题目情景

在森林和大片草地上面发生火灾是十分可怕的事情，因为火焰会点燃周围的其他树木和草，导致火势愈演愈烈。

为了防止森林大火的蔓延，通常会每隔一段距离设置一个林区防火带，比如把一定区域的树木砍掉，这样火焰遇到空旷的区域的时候就无法继续蔓延下去。

现在Doge想要详细了解防火带的作用，进行了一个模拟的防火实验。实验中对模拟的火柴棍进行点火。火柴棍长短不一，但是燃烧的速度都是1cm每秒。当火柴棍烧尽时，火势会蔓延至相邻的火柴棍上面。如果一侧没有火柴棍，则无法蔓延。

现在请你记录模拟火势蔓延的过程，输出实验结束时剩下火柴棍的长度。

输入格式

第一行，一个正整数n，代表实验时位置的个数，包括空白的防火带区域

接下来第二行，n个非负整数，这n个数字表示每个位置的火柴棍长度(单位cm)，输入0表示空白防火带区域，开始的一个记为位置1，最后一个记为位置n，依此类推

第三行，两个正整数end和m，代表实验结束时间和点火的次数

接下来m行，每行两个正整数，分别代表每次点火的时间t和位置pos

输出格式

n个数字，表示实验结束的时候，每个位置上火柴的剩余长度，空白的防火区域也输出0

样例

输入样例1

10
1 2 3 4 5 6 7 8 9 10
6 2
1 4
1 10

输出样例1

1 2 2 0 4 6 7 8 9 5

输入样例2

10
1 2 0 4 0 6 7 8 9 10
6 2
1 4
1 10

输出样例2

1 2 0 0 0 6 7 8 9 5

数据范围与提示

所有的点火时间t均不超过结束时间end，所有点火位置pos均不超过位置总数n

n和m不超过20