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 number1 dances with a girl number 1, boy number 2 dances with a girl number 2 and 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:

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

The first line of the input contains two integers n andq (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 thatn is even.

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

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.

6 31 221 2Output
4 3 6 5 2 1Input
2 31 121 -2Output
1 2Input
4 221 3Output
1 4 3 2
題目大意：
一共有N對男女在跳舞，站成一個圈，一開始i號男生和i號女生在一起跳，過程中有Q次改變位子的操作，女孩一直不動，男生會動。
1 x：表示所有男生要移動X個位子，對應X>0是順時針，否者就是逆時針。
2：表示位子【x，x+1】的男生交換位子 （x從1開始，X包括：【1,3,5,7.............】）。
問最終每個位子上都是什么編號的男生。
保證N是偶數；
思路：
1、直接暴力的話問題的時間復雜度是O（nq）；顯然直接搞是TLE的，那么考慮思維優化。
首先我們列舉出這個問題的一些特性：①對于操作1，就是所有男生在轉圈的移動，顯然對于每個人來講，都要進行。
②對于操作2，就是將所有奇數位子上的男生換到+1的位子上，將所有偶數位子上的男生換到-1的位子上。
2、一開始想做這個題的時候一門心思的考慮怎樣操作能夠抵消掉一些成對出現的操作2上來。對于這個問題，我萌在紙上多寫出幾種情況不難發現，對于操作的時候，所有的奇數編號的男生對于操作2的移動反向都是相同的。而且所有的偶數編號的男生對于操作2的移動反向也是相同的。
那么我們找到了一個重要的規律：
由于操作的特性使得奇數編號的男孩子們肯定不會出現相鄰的情況，又因為這個特性，那么保證了奇數編號男生的相對位子。
比如1號男生最終到達位子X，那么3號男生到達的位子肯定是X順時針+2的位子上，那么5號男生到達的位子肯定是X順時針+4的位子上。
那么同理，對于偶數編號的男孩子們肯定也不會出現相鄰的情況，那么又因為這個特性，也保證了偶數編號男生的相對位子。
3、那么我們接下來只要維護編號1的男孩子交換的過程，得到最終的位子，就能輕易的得到編號為3.5.7..................奇數編號的男生們的位子。
同理，我們只要維護編號2的男孩子交換的過程，得到最終的位子，就能輕易的得到編號為2.4.6...........偶數編號的男生們的位子。
Ac代碼：
#include<stdio.h>#include<string.h>using namespace std;int a[1000600];int p[2000600][2];int ans[1000600];int main(){    int n,q;    while(~scanf("%d%d",&n,&q))    {        int now=1;        int now2=2;        memset(ans,0,sizeof(ans));        for(int i=0;i<q;i++)        {            scanf("%d",&p[i][0]);            if(p[i][0]==1)            {                scanf("%d",&p[i][1]);                now+=p[i][1];                now2+=p[i][1];            }            if(p[i][0]==2)            {                if(now%2==1)now+=1;                else now-=1;                if(now2%2==1)now2+=1;                else now2-=1;            }            if(now>n)now-=n;            if(now<1)now+=n;            if(now2>n)now2-=n;            if(now2<1)now2+=n;        }        int cnt=1;        int t=n/2;        while(t--)        {            ans[now]=cnt;            ans[now2]=cnt+1;            cnt+=2;            now+=2;            now2+=2;            if(now>n)now-=n;            if(now<1)now+=n;            if(now2>n)now2-=n;            if(now2<1)now2+=n;        }        for(int i=1;i<=n;i++)        {            printf("%d ",ans[i]);        }        printf("/n");    }}