Statement is not available in English language
3. Высокие горы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В мире существует огромное количество горных систем. Самые высокие из них, как правило, образовались в течение последних 50 млн. лет и называются молодыми. Ученые собрали статистику о высоте гор в виде неубывающего массива чисел — $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, означающих высоты гор в сантиметрах.

Оказалось, что можно предсказать высоты гор в будущем. Для каждого года $$$j$$$ в течение $$$q$$$ последующих лет ученые предположили, что $$$k_j$$$ самых высоких гор вырастут на $$$x_j$$$ сантиметров.

Ученые предоставили вам необходимую информацию и попросили вас узнать, какими будут высоты гор через $$$q$$$ лет. Напишите программу, которая поможет найти искомые высоты.

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

На вход в первой строке подается натуральное число $$$n$$$ $$$(1 \leqslant n \leqslant 10^5)$$$ — количество исследуемых гор. Во второй строке идут $$$n$$$ чисел — $$$a_i$$$ $$$(1 \leqslant a_i \leqslant 10^9)$$$ — текущие высоты гор в сантиметрах.

В третьей строке находится число $$$q$$$ $$$(1 \leqslant q \leqslant 10^5)$$$ — количество последующих лет, в которые происходили изменения. Каждая из следующих $$$q$$$ строк состоит из 2 чисел — $$$k_j$$$ и $$$x_j$$$ $$$(1 \leqslant k_j \leqslant n$$$, $$$1 \leqslant x_j \leqslant 10^4)$$$, где $$$k_j$$$ — количество самых высоких гор, которые вырастут в $$$j$$$-й год, а $$$x_j$$$ — высота, на которую они увеличатся.

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

Нужно вывести $$$n$$$ чисел — высоты гор через $$$q$$$ лет в сантиметрах в порядке неубывания чисел.

Пример
Входные данные
3
1000 2000 3000
2
2 2000
1 3000
Выходные данные
1000 4000 8000
Примечание

В первом примере всего 3 горы высотой 1000, 2000 и 3000 сантиметров. В следующем году высоты второй и третьей гор увеличатся на 2000 сантиметров, а через год — вырастет только третья гора на 3000 сантиметров