D. OutOfMemoryError
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Бесси есть массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Бесси выполняет $$$m$$$ операций над массивом. $$$i$$$-я операция устанавливает $$$a_{b_i} = a_{b_i} + c_i$$$.

К сожалению, из-за растущих затрат на оперативную память компьютер Бесси имеет ограниченную память, и каждый раз, когда любой элемент массива превышает $$$h$$$, её компьютер зависает, и каждый элемент массива сбрасывается на своё исходное значение.

После выполнения всех операций выведите массив $$$a$$$.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, m, h$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \leq h \leq 10^9$$$) — длину массива $$$a$$$, количество выполненных операций и максимальное значение, которое компьютер Бесси может хранить без зависания.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le h$$$) — массив $$$a$$$.

Следующие $$$m$$$ строк содержат по два целых числа $$$b_i, c_i$$$ ($$$1 \leq b_i \leq n$$$, $$$0 \leq c_i \leq 10^9$$$) — операции, которые Бесси выполняет над массивом.

Гарантируется, что сумма $$$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$$$ изменяется следующим образом:

  • Перед всеми операциями, $$$a = [1, 2, 1]$$$.
  • После первой операции, $$$a = [5, 2, 1]$$$.
  • После второй операции, $$$a = [5, 6, 1]$$$, но так как $$$6 \gt h$$$, компьютер зависает, и $$$a = [1, 2, 1]$$$.
  • После третьей операции, $$$a = [1, 2, 4]$$$.
  • После четвертой операции, $$$a = [1, 2, 4]$$$.

Для третьего набора входных данных каждая операция вызывает зависание компьютера, поэтому $$$a = [1, 0, 0, 0]$$$.