Blake 每个月都会收到包含“Blake Technologies”公司主要经济指标的报告。该公司生产n种商品。对于每一项,最终报告中都只有一个整数,表示相应的收入。在报告到达 Blake 之前,它会经过 m 位经理的手。他们每个人都可以按某种顺序重新排列元素。即,第 i 个经理要么按非降序或非升序对第一个 ri 编号进行排序,然后将报告传递给经理 i + 1,或直接传递给 Blake(如果该经理有编号 i = m)。
“Blake Technologies”的员工正在准备报告。你知道长度为n的初始序列ai和每个管理者的描述,即值ri和他最喜欢的顺序。您需要加快该过程并确定最终报告的外观。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200 000)——分别是报告中的商品数量和管理者数量。
第二行包含 n 个整数 ai (|ai| ≤ 109) — 到达第一位经理之前的初始报告。
然后接下来的 m 行是经理将要执行的操作的描述。这些行中的第 i 行包含两个整数 ti 和 ri ($$t_{i} \in \{1,2\}$$, 1 ≤ ri ≤ n),这意味着第 i 个管理器按非降序(如果 ti = 1)或非升序(如果 ti = 2)对第一个 ri 数字进行排序。
输出
打印 n 个整数——最终报告,该报告将由编号 m 的经理传递给 Blake。
示例
输入 #1
3 1 1 2 3 2 2
输出 #1
2 1 3
输入 #2
4 2 1 2 4 3 2 3 1 2
输出 #2
2 4 1 3
注意
在第一个示例中,初始报告如下所示:1 2 3。在第一位经理之后,前两个数字被调换:2 1 3。报告以这种形式发送给 Blake。
在第二个示例中,原始报告如下:1 2 4 3。在第一个经理之后,报告更改为:4 2 1 3。在第二个经理之后,报告更改为:2 4 1 3。该报告已移交给 Blake。