Multiply Query#496

Multiply Query

1 seconde
256 mégaoctets
Hard

Mister IP has two arrays and , both of length , and a integer . Initially b_i = 0 for all 1 \le i \le n.

Now he wants to handle updates of the following form:

For the -th update, three integers l_i, r_i, x_i are given. Then you do the following

  1. for each l_i \le j \le r_i, do a_j := a_j \cdot x.

  2. after this, for each 1 \le k \le n (note that for all , not only between and ), if a_k \ge Y, add to b_k.

Now, after performing all of the updates, Mister IP wants to know the values of b_i for each 1 \le i \le n.

Input

The first line contains three integers (2 \le n \le 2 \cdot 10^5), (1 \le q \le 2 \cdot 10^5), (2 \le Y \le 10^6) — the number of elements in arrays and , the number of updates, and the parameter .

The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i < Y).

Each of the next lines contains three integers l_i, r_i, x_i (1 \le l_i \le r_i \le n, 1 \le x_i < Y).

Output

Output integers in one line  — the values of b_1, b_2, \dots, b_n after handling all updates.

Examples

Example 1

Loading
Loading

Note

After the first update, array looks as follows: [1, 3, 3, 3, 1]. Array b = [0, 0, 0, 0, 0].

After the second update, a = [2, 6, 6, 3, 1]. Array b = [0, 1, 1, 0, 0].

After the third update, a = [2, 6, 6, 3, 1]. Array b = [0, 2, 2, 0, 0].

After the fourth update, a = [4, 12, 12, 6, 2]. Array b = [0, 3, 3, 1, 0].

After the fifth update, a = [8, 24, 24, 12, 4]. Array b = [1, 4, 4, 2, 0].