题目描述

给定序列 $(a_1,a_2,⋅⋅⋅,a_n)=(1,2,⋅⋅⋅,n)$，即 $a_i=i$。

小蓝将对这个序列进行 $m$ 次操作，每次可能是将 $a_1,a_2,⋯ ,a_{q_i}$ 降序排列，或者将 $a_{q_i},a_{q_{i+1}},⋯ ,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}},⋯ ,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)$ 步操作后相同，因为前两个数已经是降序了。

评测用例规模与约定

对于 $30\%$ 的评测用例，$n,m≤1000$；

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

对于所有评测用例，$1≤n,m≤100000，0≤p_i≤1，1≤q<i≤n$。