有一个长度为 $n$ 的序列，$m$ 次操作，$2$ 个参数 $t$，$r$。 如果 $t=1$ 则将下标为 1~r 的数升序排列，$t=2$ 则将下标为 1~r 的数降序排序，求最后的数列。

输入

3 1
1 2 3
2 2

输出

2 1 3