小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