题目描述

首先输入一个长度为 $n$ 的数组：$a_1\sim a_n$。
紧接着有 $m$ 次操作，每次操作都会给定一个 $x,y$，要求在当前数组的 $a_x$ 与 $a_{x+1}$ 之间插入 $y$。
输出最终的数组：$a_1\sim a_{n+m}$。

输入格式

第一行一个整数 $n$。
接下来一行 $n$ 个整数，即 $a_1\sim a_n$。
第三行包括一个整数 $m$。
接下来 $m$ 行，每行包括两个整数 $x,y$ 含义如题目所述。

输出格式

一行 $n+m$ 个整数，表示最终的数组：$a_1\sim a_{n+m}$。

4
1 2 3 4
2
1 5
3 6

1 5 2 6 3 4

样例解释

• 第一次操作后数组变成了：1 5 2 3 4
• 第二次操作后数组变成了：1 5 2 6 3 4

数据规模与约定

对于 $100\%$ 的数据保证：

• $1 \le n,m \le 10^4$
• $1 \le a_i \le 10^9$
• 每次操作的 $x$ 小于操作之前的数组长度
• $1 \le y \le 10^9$