题目描述

给定 $n$ 个整数组成的序列和 $m$ 个操作，每个操作给定 $t_i$ 和 $r_i$，操作分为两种：

• $t_i$ 为 $1$，则将前 $r_i$ 个数按照连续不减序（从小到大）排列；
• $t_i$ 为 $2$，则将前 $r_i$ 个数按照连续不增序（从大到小）排列。

求 $m$ 次操作过后的序列。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 2\cdot 10^5$。

第二行 $n$ 个整数 $a_i$，$|a_i|\le 10^9$，表示初始序列。

接下来 $m$ 行，每行一个操作。

输出格式

在一行中输出 $n$ 个整数，表示 $m$ 次操作后的序列。

3 1
1 2 3
2 2

2 1 3

4 2
1 2 4 3
2 3
1 2

2 4 1 3