题目描述

_rqy 得到了一副魔法卡牌！

魔法卡牌共有 $n$ 张，每张卡牌上都写着一个数字，没有两张卡牌上的数字相同。

最初，卡牌被摞成一叠，从上到下的第 $i$ 张卡牌上的数字为 $a_i$。

随后，_rqy 对卡牌进行了 $q$ 次洗牌。洗牌的方法是这样的：将写有数字 $l$ 的卡牌与写有数字 $r$ 的卡牌之间的所有卡牌（包含写有数字 $l$ 和 $r$ 的卡牌）从牌堆中取出，再插入到牌堆的最下方。

洗牌结束后，_rqy 告诉你，她能把现在的牌序倒背如流！你心想：如果我能写出一个程序实现同样的功能，四舍五入我就和 _rqy 一样厉害！

请你向 _rqy 发起挑战吧！

输入格式

第一行两个正整数 $n$ ($2 \leq n \leq 10^5$) 和 $q$ ($1 \leq q \leq 10^5$)， 用一个空格隔开，表示有 $n$ 张卡牌，进行了 $q$ 次洗牌。

第二行 $n$ 个正整数，用一个空格隔开，第 $i$ 个数 $a_i$ ($1 \leq a_i \leq n$) 表示最初从上到下的第 $i$ 张卡牌上的数字。保证没有两张卡牌上的数字相同。

随后 $q$ 行，每行两个正整数 $l$ ($1 \leq l \leq n$) 和 $r$ ($1 \leq r \leq n$)，用一个空格隔开。若 $l \neq r$，保证此时写有数字 $l$ 的卡牌位于写有数字 $r$ 的卡牌上方。

输出格式

一行 $n$ 个正整数 $p_i$，用一个空格隔开，表示最终的牌序。

由于 _rqy 对牌序倒背如流，所以你需要从下到上输出最终的牌序。

样例

样例输入

5 1
3 1 2 5 4
1 5

样例输出

5 2 1 4 3

数据范围与提示

若写有数字 $r$ 的卡牌已经在牌堆最下方，则该次洗牌对牌序无影响。