← 返回题目列表

Codeforces · 641/C

C. 小阿尔乔姆和舞蹈

中文机器翻译题面 查看原题

小Artem喜欢跳舞。在所有舞蹈中,阿尔乔姆最喜欢鲁埃达舞(rueda)——一种古巴舞蹈,由成对的男孩和女孩围成一个圆圈,一起跳舞。

更详细一点,有n对男孩和女孩站成一圈。最初,1 号男孩与 1 号女孩跳舞,2 号男孩与 2 号女孩跳舞,依此类推。女孩按顺时针顺序编号。舞蹈期间会宣布不同的动作,所有双人舞都会表演这些动作。表演动作时,男生沿着圆圈移动,而女生则始终保持在初始位置。为了解决这个问题,我们考虑两种不同类型的移动:

1. 公布x值和某个方向,所有男孩向相应方向移动x个位置。
2. 与偶数索引女孩跳舞的男孩与与奇数索引女孩跳舞的男孩交换位置。即与 1 号女孩跳舞的人与与 2 号女孩跳舞的人交换,与 3 号女孩跳舞的人与与 4 号女孩跳舞的人交换,依此类推。保证n是偶数。

你的任务是确定每个男孩的最终位置。

输入

输入的第一行包含两个整数 n 和 q (2 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 2 000 000)——分别是 rueda 中的情侣数量和要执行的命令数量。保证n是偶数。

接下来的 q 行包含命令的描述。每个命令的类型首先为整数 1 或 2。第一类命令为x(-n≤x≤n),其中0≤x≤n表示所有男生顺时针方向移动x个女生,而-x表示所有男生逆时针方向移动x个位置。对于第二类型的命令没有其他输入。

输出

输出n个整数,其中第i个整数应等于执行完所有q个动作后第i个女孩正在跳舞的男孩的索引。

示例

输入 #1

6 3
1 2
2
1 2

输出 #1

4 3 6 5 2 1

输入 #2

2 3
1 1
2
1 -2

输出 #2

1 2

输入 #3

4 2
2
1 3

输出 #3

1 4 3 2