Background

n 个小朋友（小朋友从 0 到 n-1 进行编号）围坐一圈玩游戏。按照顺时针方向依次给 n 个位置编号，也是从 0 到 ​n-1​。最初，第 0 号小朋友在第 0 号位置，第 1 号小朋友在第 1 号位置，……，依此类推。

游戏规则如下：每一轮给出两个整数 ​a​、​b​。若 a 的值等于 ​1​，则所有小朋友依次逆时．．

针．转 b 个位置；若 a 的值等于 ​2​，则所有小朋友依次顺时针．．．转 b 个位置。

比如：a=2，b=3，那么第 0 号位置上的小朋友顺时针转到第 3 号位置，第 1 号位置上的小朋友顺时针转到第 4 号位置，……，第 n-3 号位置上的小朋友顺时针转到第 0 号位置，第 n-2 号位置上的小朋友顺时针转到第 1 号位置，第 n-1 号位置上的小朋友顺时针转到第 2 号位置，一轮转圈结束。

依照上面的游戏规则，请问进行 q 轮后，第 0 到 n-1 号位置上的小朋友的编号分别是什么？

Input

【输入数据】输入文件 ​circle.in​：输入从文件中读取，输入共 q+1 行。

第 1 行是两个整数 n 和 q（1≤n≤100000, 0≤q≤200000），表示 n 个小朋友要进行 q 轮转圈游戏，两个整数间用空格分隔。

第 2 行到第 q+1 行，每行两个用空格分隔的整数。其中第 i+1 行两个整数为 ai 和 b（i~ a​i=1 或者 a​i=2, 0≤bi~≤n-1），表示第 i 轮转圈的信息。若 ​a​i​=1，则所有小朋友依次向逆时针．．．方向转 bi 个位置，若 ​a​i=2​，则所有小朋友依次向顺时针．．．方向转 bi 个位置。

Output

【输出数据】

输出文件 ​circle.out​：结果输出到文件中。

输出共 n 行，每行包含一个整数，第 i 行整数表示经过转圈后第 i-1 号位置上的小朋友的编号。

Samples

4 1 
2 3

1 
2 
3 
0

5 3 
1 1 
2 2 
1 3 

2 
3 
4 
0 
1 

Limitation

【样例 1 解释】

4个小朋友参加转圈游戏，转圈共进行了 1 轮，在这轮转圈游戏中，所有小朋友依次向顺时针方向转了 3 个位置，第 0 号小朋友转到第 3 号位置，第 1 号小朋友转到了第 0 号位置，第 2 号小朋友转到了第 1 号位置，第 3 号小朋友转到了第 2 号位置，所以最后第 0 号位置到第 3 号位置上的小朋友编号分别是 1，2，3，0。

【样例 2 解释】

5个小朋友参加转圈游戏，转圈共进行了 3 轮。在第 1 轮转圈游戏中，所有小朋友依次向逆时针方向转了 1 个位置。在第 2 轮转圈游戏中，所有小朋友依次向顺时针方向转了 2 个位置。在第 3 轮转圈游戏中，所有小朋友依次向逆时针方向转了 3 个位置。所以最后第 0 号位置到第 4 号位置上的小朋友编号分别是 2，3，4，0，1。

【数据范围约定】

对于 70%的数据，1≤n≤1000，0≤q≤2000。

对于 100%的数据，1≤n≤100000，0≤q≤200000。