问题描述

给定序列$(a_1, a_2, \cdots ,a_n) = (1, 2, \cdots, n)$,即$a_i = i$。 小蓝将对这个序列进行$m$次操作，每次可能是将$a_1, a_2, \cdots, a_{q_i}$降序排列，或者将$a_{q_i}, a_{q_i + 1}, \cdots, a_n$升序排序。 请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数$n,m$，分别表示序列的长度和操作次数。

接下来$m$行描述对序列的操作，其中第$i$行包含两个整数$p_i, q_i$表示操作类型和参数。当$p_i= 0$时，表示将$a_1, a_2, \cdots, a_{q_i}$降序排列；当$p_i = 1$时，表示将$a_{q_i}, q_{q_i + 1}, \cdots, a_n$升序排列。

输出格式

输出一行，包含$n$个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

样例输入输出

3 3
0 3
1 2
0 2

3 1 2

样例说明

原数列为$(1, 2, 3)$。

第1步后为$(3, 2,1)$。

第2步后为$(3, 1, 2)$。

第3步后为$(3, 1, 2)$。与第2步操作后相同，因为前两个数已经是降序了。

评测用例规模与规定

对于$30\%$的评测样例,$n, m \leqslant 1000$。

对于$60\%$的评测样例,$n, m \leqslant 3000$。

对于$100\%$的评测样例，$1 \leqslant n, m \leqslant 100000, 0 \leqslant p_i \leqslant 1, 1 \leqslant q_i \leqslant n$。

运行限制

• 最大运行时间：$2s$
• 最大运行内存：$256M$