【题目描述】

给定一个长度为 $n$ 的排列。

进行 $m$ 次操作，每次给出两个不同的位置 $x,y$，将操作开始前位于第 $x$ 个位置的元素移到位于第 $y$ 个位置的元素前方，其余元素的相对顺序保持不变。

请输出所有操作结束后的排列。

【输入描述】

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个整数 $a_i$，表示初始排列。

接下来 $m$ 行，每行输入两个整数 $x,y$，表示一次操作。

保证：

• $1\le n,m\le 1000$；
• $a_i$ 是 $1$ 到 $n$ 的一个排列；
• $1\le x,y\le n$ 且 $x\ne y$。

【输出描述】

输出一行 $n$ 个整数，表示最终排列，相邻两个整数之间用一个空格分隔。

【样例 1】

【样例 1 输入】

5 3
1 2 3 4 5
5 2
1 4
2 5

【样例 1 输出】

5 1 3 2 4

【样例 1 解释】

第一次操作后序列为：1 5 2 3 4；

第二次操作后序列为：5 2 1 3 4；

第三次操作后序列为：5 1 3 2 4。

【样例 2】

【样例 2 输入】

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

【样例 2 输出】

1 3 6 4 2 5