题目描述

在二次元像素世界中，有一条原长度为N的贪吃蛇snake，它吃到了m个苹果，每吃到一个苹果会在长出一节新的身体。

贪吃蛇的身体刚开始由N个部分组成，每个部分都有属于这部分的数字编号，数字编号可能重复。

现在给出每次吃苹果时长出身体的所在位置和新一节身体的数字编号，请你按顺序输出最后贪吃蛇全身的身体编号

输入格式

一个数字N，代表原身长

N个数字，snake[i]代表第i节身体的数字编号

一个数字M，代表苹果数量

M组数字，每组两个数pos[j]和num[j]，分别代表吃第j个苹果会在第pos[j]节前长出一节身体，且新身体的数字编号为num[j]。其中的pos[j]必定不大于贪吃蛇当前的长度。

输出格式

N+M个数字，snake[i]分别代表每节身体的数字编号

输入样例

10
1 2 3 4 5 6 7 8 9 0
3
3 33
6 66
8 88

输出样例

1 2 33 3 4 66 5 88 6 7 8 9 0

数据范围

N和M为1000以内的正整数，num[j]均在整型int范围以内