CodeForces

D. Little Artem and Dance

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Artem is fond of dancing. Most of all dances Artem likes rueda — Cuban dance that is danced by pairs of boys and girls forming a circle and dancing together.

More detailed, there are n pairs of boys and girls standing in a circle. Initially, boy number 1 dances with a girl number 1, boy number 2 dances with a girl number 2and so on. Girls are numbered in the clockwise order. During the dance different moves are announced and all pairs perform this moves. While performing moves boys move along the circle, while girls always stay at their initial position. For the purpose of this problem we consider two different types of moves:

Value x and some direction are announced, and all boys move x positions in the corresponding direction.
Boys dancing with even-indexed girls swap positions with boys who are dancing with odd-indexed girls. That is the one who was dancing with the girl 1 swaps with the one who was dancing with the girl number 2, while the one who was dancing with girl number 3 swaps with the one who was dancing with the girl number 4 and so one. It's guaranteed that n is even.

Your task is to determine the final position of each boy.

Input

The first line of the input contains two integers n and q (2 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 2 000 000) — the number of couples in the rueda and the number of commands to perform, respectively. It's guaranteed that n is even.

Next q lines contain the descriptions of the commands. Each command has type as the integer 1 or 2 first. Command of the first type is given as x ( - n ≤ x ≤ n), where 0 ≤ x ≤ n means all boys moves x girls in clockwise direction, while - x means all boys move x positions in counter-clockwise direction. There is no other input for commands of the second type.

Output

Output n integers, the i-th of them should be equal to the index of boy the i-th girl is dancing with after performing all q moves.

Examples

Input

Output

4 3 6 5 2 1

Input

Output

1 2

Input

4 2
2
1 3

Output

1 4 3 2

题意：有n对男女，原本1号男对应1号女，依次类推，一一对应。有p次操作。
每次操作都有分为两种类型。
第一种类型：移动男孩x位子，x为正则为顺时针，x为负则为逆时针（女孩是不动的在这题中）。
第二种类型：1号女孩对应的男孩和2号女孩对应的男孩交换，依次类推，3号女孩对应的男孩和4号女孩对应的男孩交换.......
最后依次输出（1-n号）女孩对应的男孩。
题解：奇数号男生走的步数是一样多的。偶数号男生走的步数也是一样多的。
第一种类型操作结果：奇数号男和偶数号男都是一样的移动x步；
第二种类型操作结果：交换相邻位子（女孩奇偶对应）的男孩。站在对应奇数女孩的男孩要向前走一步，站在对应偶数女孩的男孩要向后退一步；（这就是这题的关键了）
废话不多说，下面直接上代码：

#include<stdio.h>
int map[1000100];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    int sum1=0;
    int sum2=0;
    while(q--)
    {
        int choose;
        scanf("%d",&choose);
        if(choose==1)
        {
            int k;
            scanf("%d",&k);
            sum1=sum1+k%n;
            sum2=sum2+k%n;
        }
        else
        {
            if(sum1%2==1)//奇数号男孩走了奇数步，说明现在对应的女孩是偶数女孩，所以交换相当于向后退一步 
            sum1--;
            else
            sum1++;
            if(sum2%2==1)//偶数号男孩走了奇数步，说明现在对应的女孩是奇数女孩，所以交换相当于向前进一步
            sum2++;
            else
            sum2--;
        }
        while(sum1<0)//防止为负数 
        sum1+=n;
        while(sum2<0)//防止为负数 
        sum2+=n;
        sum1=sum1%n; 
        sum2=sum2%n;
    }
    for(int i=0;i<n;i=i+2)//tip:这里也循环可以写成1-n的，但是需要特判i%n==0因为此时的结果时在n位子而不是0 
    {
        map[(i+sum1)%n]=i+1;//此处的理解：i=0时可以看成起始是1号男移动后的位子 
        map[((i+1)+sum2)%n]=i+2;//此处的理解：i=0时可以看成是2号男移动后的位子 
    }
    for (int i=0;i<n;i++)
    {
        if(i==0)
        printf("%d",map[i]);
        else
        printf(" %d",map[i]); 
    }
    printf("
");
 }