URI Online Judge | 1399
# Array Transformer

**Timelimit: 3**

By Rujia Liu China

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).

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 ≤ **L** ≤ **R** ≤ **n**, 1 ≤** v** ≤ **u**, 1 ≤ **p** ≤ **n**).

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

Sample Input | Sample Output |

10 1 11 |
1 |