题目描述

你是一名探险家，最近在一座古老的城堡中发现了一本神秘的魔法书。这本书中记录了一种奇异的咒语，可以操控一个神秘的数字序列。

初始时，你面前有一个长度为 $n$ 的数字序列。你需要依次执行以下的操作：

1. 插入数字：通过施展一个咒语，你可以在指定位置的后面插入一个数字。

每次施展咒语后，序列的状态都会发生变化，你需要根据给定的操作顺序，正确执行每个咒语并记录下序列的变化结果。

输入格式

第一行包含一个整数 $n$，表示初始序列的长度。

第二行包含 $n$ 个整数，表示初始序列中的每个数字。

第三行包含一个整数 $m$，表示操作的总数。

接下来的 $m$ 行，每行包含两个整数 $k$ 和 $x$，表示在第 $k$ 个数后面插入数字 $x$。数据保证所有的 $k$ 都是合法的。

输出格式

输出经过所有操作后的最终序列，数字之间用空格分隔。

样例

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

1 2 6 3 7 8 4 5

4
9 8 7 6
2
1 10
3 11

9 10 8 11 7 6

提示

样例1解释

1. 初始序列为：1 2 3 4 5
2. 2 6：在第2个数（2）后面插入数字6，序列变为：1 2 6 3 4 5
3. 4 7：在第4个数（3）后面插入数字7，序列变为：1 2 6 3 7 4 5
4. 5 8：在第5个数（7）后面插入数字8，序列变为：1 2 6 3 7 8 4 5

样例2解释

1. 初始序列为：9 8 7 6
2. 1 10：在第1个数（9）后面插入数字10，序列变为：9 10 8 7 6
3. 3 11：在第3个数（8）后面插入数字11，序列变为：9 10 8 11 7 6

数据范围