题目描述

Bessie 有一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。她会对数组执行 $m$ 次操作，第 $i$ 次操作令 $a_{b_i}=a_{b_i}+c_i$。

不幸的是，由于内存价格上涨，Bessie 的电脑内存有限：只要数组中任意一个元素大于 $h$，电脑就会崩溃，并且数组中所有元素都会被重置为最初的值。

所有操作执行完后，输出数组 $a$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含三个整数 $n,m,h$，分别表示数组长度、操作次数以及电脑不会崩溃时可存储的最大值。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始数组。

接下来 $m$ 行，每行包含两个整数 $b_i,c_i$，表示一次操作。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出所有操作完成后的数组 $a$。

样例

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

1 2 4
1 1 1 1 1
1 0 0 0

样例说明

第一组测试数据中：

• 初始时 $a=[1,2,1]$。
• 第一次操作后 $a=[5,2,1]$。
• 第二次操作后 $a=[5,6,1]$，由于 $6>h$，电脑崩溃，数组重置为 $[1,2,1]$。
• 第三次操作后 $a=[1,2,4]$。
• 第四次操作不会改变数组。

第三组测试数据中，每次操作都会导致电脑崩溃，因此最终数组为 $[1,0,0,0]$。

数据范围

• $1 \le t \le 10^4$
• $1 \le n,m \le 2\cdot 10^5$
• $1 \le h \le 10^9$
• $0 \le a_i \le h$
• $1 \le b_i \le n$
• $0 \le c_i \le 10^9$
• 所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $2\cdot 10^5$

来源

Codeforces Round 1074 (Div. 4), Problem D - OutOfMemoryError