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
for each l_i \le j \le r_i, do a_j := a_j \cdot x.
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.
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 integers in one line — the values of b_1, b_2, \dots, b_n after handling all updates.
Example 1
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].