← 返回题目列表

Codeforces · 631/C

C. 报告

中文机器翻译题面 查看原题

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。