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

输入的第一行包含两个整数n,m，分别表示序列的长度和操作次数。 
接下来m行描述对序列的操作，其中第i行包含两个整数pi, qi 表示操作类型和参数。当pi = 0 时，表示将a1, a2, · · · , aqi 降序排列；当pi = 1时，表示将aqi, aqi+1, · · · , an 升序排列。

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

【样例说明】

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

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

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

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

【评测用例规模与约定】

对于30%的评测用例, n,m≤1000;

对于60%的评测用例, n,m≤5000;

对于所有评测用例, 1≤n,m≤10^5,0≤pi​≤1,1≤qi​≤n 。