该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小吴、小张两个摸金校尉和你偶然的机会发现了一座未被开发的古墓。进入古墓后，肉眼可见的辉煌装饰、雕刻、壁画，让你们来了兴致，一拍即合决定深入调查，挖掘古墓深处的财宝。

走到走廊的尽头，你们发现了一个巨大的石门，无论如何用力都无法打开，但石门上似乎有一些机关，破解机关说不定可以打开石门！

题目描述

机关上有一连串的 $n$ 个数字被放在独立的格子里，格子编号分别为 $1 \sim n$，并且每个数字都不相同，每个数字的格子还都可以移动。

随后你们又发现了 $m$ 组数字，每组数字是 $2$ 个数字 $l、r$，并且总是 $1 \leq l < r \leq n$，又根据机关上的图案，你们猜测可能是需要对编号 $l \sim r$ 范围内的数字进行一些操作：把每个数字向后移动一个格子，编号为 $r$ 的格子的数字则需要挪到编号为 $l$ 的格子里。

你们决定实践起来，但数字实在太多了，操作起来有点麻烦，于是决定由你来编写一个程序，找出移动后的 $n$ 个数字会变成什么样子。

输入格式

第 $1$ 行输入一个整数 $n(10 \leq n \leq 10^4)$，表示数字的个数。

接下来一行，输入 $n$ 个整数，用空格隔开，每个整数都在 $1 \sim 10^6$ 范围内。

紧接着一行，输入一个整数 $m(1 \leq m \leq 10^4)$，表示操作的次数。

接下来 $m$ 行，每行 $2$ 个整数 $l、r(1 \leq l < r \leq n)$，分别表示需要操作的格子的编号范围。

输出格式

输出一行 $n$ 个整数，表示移动后的 $n$ 个格子里的数字。

输入输出样例 #1

输入 #1

5
1 2 3 4 5
1
2 4

输出 #1

1 4 2 3 5

输入输出样例 #2

输入 #2

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

输出 #2

2 7 1 4 6 5