CF641C Little Artem and Dance

小 Artem 喜欢跳舞。他最喜欢的舞蹈是 rueda —— 一种古巴舞蹈，男孩和女孩成对围成一个圆圈一起舞蹈。 具体来说，有 $n$ 对男孩和女孩围成一个圆圈站着。最初，第 $1$ 号男孩与第 $1$ 号女孩共舞，第 $2$ 号男孩与第 $2$ 号女孩共舞，依此类推。所有女孩按照顺时针方向编号。在舞蹈过程中，不同的动作会被依次宣布，所有的情侣都会同时进行动作。在动作中，男孩们会沿着圆圈移动，而女孩们始终站在原位。对于本题，有两种不同类型的动作： 1. 公布一个值 $x$ 以及一个方向，所有男孩朝对应方向移动 $x$ 个位置。 2. 与偶数编号女孩共舞的男孩与与奇数编号女孩共舞的男孩交换位置。也就是说，与第 $1$ 号女孩共舞的男孩与与第 $2$ 号女孩共舞的男孩交换位置，与第 $3$ 号女孩共舞的男孩与与第 $4$ 号女孩共舞的男孩交换位置，依此类推。保证 $n$ 为偶数。 你的任务是，经过所有 $q$ 次操作后，输出每个女孩最终与哪一位男孩共舞。

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 1000000$，$1 \leq q \leq 2000000$）—— rueda 中情侣的数量和需要执行的命令数量。保证 $n$ 是偶数。 接下来的 $q$ 行给出命令的描述。每个命令首先有一个类型 $1$ 或 $2$。第一类命令形式为 $1\ x$（$-n \leq x \leq n$），其中 $0 \leq x \leq n$ 表示所有男孩顺时针移动 $x$ 个女孩，$-x$ 表示所有男孩逆时针移动 $x$ 个位置。第二类命令形式为 $2$（不含其它输入）。

输出 $n$ 个整数，第 $i$ 个数表示在执行完所有 $q$ 次操作后，第 $i$ 号女孩正在与哪一位男孩共舞。

由 ChatGPT 5 翻译