CF2185D OutOfMemoryError

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