A. Шаасс и Осколы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Шаасс решил поохотиться на птиц. Есть n электрических проводов, параллельных друг другу. Провода пронумерованы от 1 до n сверху вниз. На каждом проводе некоторое количество осколов сидят в рядок, на i-ом проводе сидит ai осколов. Осколы — это такие вкуснейшие птицы, они гнездятся рядом с Шаассом.

Иногда Шаассу удается подстрелить одну птицу, птица умирает (обозначим номер провода, на котором сидела эта птица как i). После чего все птицы слева от нее на проводе i пугаются и перепрыгивают вверх на провод номер i - 1. Если выше проводов нет, то они улетают. Также, все птицы справа от подстреленной перепрыгивают вниз на провод i + 1, а если такого провода нет, то они улетают.

Шаасс подстрелил m птиц. Зная изначальное количество птиц на каждом проводе, скажите, сколько птиц будет сидеть на каждом проводе после охоты.

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

Первая строка входных данных содержит целое число n, (1 ≤ n ≤ 100). Следующая строка содержит разделенные пробелом целые числа a1, a2, ..., an, (0 ≤ ai ≤ 100).

В третьей строке записано целое число m, (0 ≤ m ≤ 100). В каждой из следующих m строк записано по два целых числа, xi и yi. Эти числа означают, что в i-ый раз Шаасс подстрелил yi-ую птицу слева на xi-ом проводе, (1 ≤ xi ≤ n, 1 ≤ yi). Гарантируется, что в этот момент на xi-ом проводе будет как минимум yi птиц.

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

В i-ой строке выведите количество птиц на i-ом проводе.

Примеры
Входные данные
5
10 10 10 10 10
5
2 5
3 13
2 12
1 13
4 6
Выходные данные
0
12
5
0
16
Входные данные
3
2 4 1
1
2 2
Выходные данные
3
0
3