D. OutOfMemoryError
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie has an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Bessie performs $$$m$$$ operations on the array. The $$$i$$$-th operation sets $$$a_{b_i} = a_{b_i} + c_i$$$.

Unfortunately, due to rising RAM costs, Bessie's computer has limited memory, and whenever any element of the array is greater than $$$h$$$, her computer crashes, and every element in the array is reset to its original value.

After all operations have been performed, output the array $$$a$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n, m, h$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \leq h \leq 10^9$$$) — the length of array $$$a$$$, the number of operations performed, and the maximum value that Bessie's computer can store without crashing.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le h$$$) — the array $$$a$$$.

The next $$$m$$$ lines contain two integers $$$b_i, c_i$$$ ($$$1 \leq b_i \leq n$$$, $$$0 \leq c_i \leq 10^9$$$) — the operations that Bessie performs on the array.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the array $$$a$$$ after all operations have been performed.

Example
Input
3
3 4 5
1 2 1
1 4
2 4
3 3
2 0
5 3 1
1 1 1 1 1
1 1
1 1
2 1
4 4 1
1 0 0 0
1 1
4 4
3 3
4 4
Output
1 2 4 
1 1 1 1 1 
1 0 0 0
Note

For the first test case, the array $$$a$$$ is changed as follows:

  • Before all operations, $$$a = [1, 2, 1]$$$.
  • After the first operation, $$$a = [5, 2, 1]$$$.
  • After the second operation, $$$a = [5, 6, 1]$$$, but since $$$6 \gt h$$$, the computer crashes, and $$$a = [1, 2, 1]$$$.
  • After the third operation, $$$a = [1, 2, 4]$$$.
  • After the fourth operation, $$$a = [1, 2, 4]$$$.

For the third test case, each operation causes the computer to crash, so $$$a = [1, 0, 0, 0]$$$.