Description

给定一串数字，用链表结构进行存储。然后给定针对该链表的若干插入操作，要求将执行插入操作后的结果输出。

Input

第一行：输入一个整数n，表示这串数字有n个（n大于等于1)。 
第二行：输入这n个整数。
第三行：输入一个整数m，表示需要执行m个插入操作。
后面m行：每行输入两个整数a和b，表示在这串数字的当前第a个数字之后插入数字b。（假设链表第一个节点编号为1）

Output

输出操作后的n+m个数字。每个数字用空格空开（最后一个数字后面没有空格，直接换行）。

Sample Input

3
2 1 3
2
1 5
1 6

Sample Output

2 6 5 1 3

HINT

最后一个输出数字的后面没有空格，直接换行

Source

NBU OJ