URI Online Judge | 1399

Array Transformer

By Rujia Liu China
Timelimit: 3

Write a program to transform an array A[1], A[2],..., A[n] according to m instructions. Each instruction (L, R, v, p) means: First, calculate how many numbers from A[L] to A[R] (inclusive) are strictly less than v, call this answer k. Then, change the value of A[p] to u*k/(R - L + 1), here we use integer division (i.e. ignoring fractional part).

Input

The first line of input contains three integer n, m, u ( 1 ≤ n ≤ 300,000, 1 ≤ m ≤ 50,000, 1 ≤ u ≤ 1,000,000,000). Each of the next n lines contains an integer A[i](1 ≤ A[i] ≤ u). Each of the next m lines contains an instruction consisting of four integers L, R, v, p ( 1 ≤ LRn, 1 ≤ vu, 1 ≤ pn).

Output

Print n lines, one for each integer, the final array.

Sample Input Sample Output

10 1 11
1
2
3
4
5
6
7
8
9
10
2 8 6 10

1
2
3
4
5
6
7
8
9
6