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). 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). For each test case, output the array (a) after all operations have been performed. 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 > 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).