双向排序

题目描述

给定序列 $(a_1, a_2, · · · , a_n) = (1, 2, · · · , 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, · · · , a_{q_i}$​​ 降序排列；当 $p_i = 1$​ 时，表示将 $a_{q_i} , a_{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 \leq 1000$；

对于 $60\%$ 的评测用例，$n, m \leq 5000$；

对于所有评测用例，$1 \leq n, m \leq 100000，0 \leq p_i \leq 1，1 \leq q_i \leq n$。