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

题目背景

小A准备品尝这些九转大肠。

题目描述

有 $n$ 个九转大肠，美味值分别为 $a_1,a_2,…,a_n$。

小A本来想好好品尝这些九转大肠，但是摄影师小B为了好看，让小A按一定顺序吃这些九转大肠。具体来说，小B发出了 $m$ 个指令，第 $i$ 个指令有两个数 $op,x$ 构成。若 $op=1$，则小A需要把第 $1…x$ 的九转大肠按美味值升序摆盘；若 $op=2$，则小A需要把第 $1…x$ 的九转大肠按美味值降序摆盘。

小A已经被小B烦得要死了，所以他不想再算他的摆盘顺序了……

输入格式

第一行一个整数 $n,m$。

第二行 $n$ 个整数 $a_i$。

接下来 $m$ 行，每行两个整数 $op,x$。

输出格式

输出 $n$ 个数，表示摆盘后各个九转大肠的美味值。

样例 #1

样例输入 #1

4 2
1 2 4 3
2 3
1 2

样例输出 #1

2 4 1 3

提示

对于 $40\%$ 的数据，$n,m \le 1000$。

对于 $100\%$ 的数据，$1 \le x \le n \le 10^5$，$1 \le m \le 10^5$，$0 \le a_i \le 10^9$，$op \in \{1,2\}$。