题目描述

若若得到了一副魔法卡牌！

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

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

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

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

请你向若若发起挑战吧！

输入格式

第一行两个正整数 $n$ 和 $q$， 用一个空格隔开，表示有 $n$ 张卡牌，进行了 $q$ 次洗牌。

第二行 $n$ 个正整数，用一个空格隔开，第 $i$ 个数 $a_i$ 表示最初从上到下的第 $i$ 张卡牌上的数字。

随后 $q$ 行，每行两个正整数 $l$ 和 $r$，用一个空格隔开。

输出格式

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

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

5 1
3 1 2 5 4
1 5

5 2 1 4 3

提示

样例解释

原牌序为 3 1 2 5 4，$1$ 到 $5$ 之间的部分为 1 2 5。

将其从牌堆中取出后再插入到最下方，此时牌序为 3 4 1 2 5。但题目要求倒序输出，于是输出为 5 2 1 4 3。

数据范围

对于 $40\%$ 的数据，满足 $n \leq 1,000$，$q \leq 1,000$。

对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^5$，$1 \leq q \leq 10^5$，$1 \leq a_i, l, r \leq n$，保证 $a_i$ 两两不同。

若 $l \neq r$，保证此时写有数字 $l$ 的卡牌位于写有数字 $r$ 的卡牌上方。

补充说明

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