题目描述

给定序列(a[1], a[2], ... , a[n]) = (1, 2, ... , n)，即a[i] = i。 小蓝将对这个序列进行m次操作，每次可能是将a[1], a[2], ... a[qi] 降序排列，或者将a[qi], a[qi+1], ... , a[n] 升序排列。 请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数n, m，分别表示序列的长度和操作次数。 接下来m行描述对序列的操作，其中第i行包含两个整数pi, qi 表示操作类型和参数。 当pi = 0 时，表示将a[1], a[2], ... a[qi] 降序排列；当pi = 1 时，表示将a[qi], a[qi+1], ... , a[n] 升序排列升序排列。 对于30% 的评测用例，n,m ≤ 1000； 对于60% 的评测用例，n,m ≤ 5000； 对于所有评测用例，1 ≤ n,m ≤ 100000, 0 ≤ ai ≤ 1，1 ≤ bi ≤ n。

输出格式

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

输入样例

3 3
0 3
1 2
0 2

输出样例

3 1 2