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.

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]$$$.

OutOfMemoryError

Examples