Pandaemonium 出了点问题。Azem 的朋友 Themis 正等着你一起去看看。

糟糕，Pandaemonium 的守卫 Erichthonios 误把你当作敌人，开始攻击你了。你能保护好自己和 Themis 直到他冷静下来吗？

为了简化问题，Themis 的防御系统有 $n$ 个排成一行的方块。所有方块的初始权重均为 $0$，且具有相同的属性。Erichthonios 将执行以下 4 种攻击 $q$ 次：

• $1\ x\ c$：Erichthonios 使用他的锁链连接第 $x$ 个方块和所有最靠近的 $2c$ 个方块，赋予它们一个新的属性（覆盖方块原有的属性）。
• $2\ x\ y$：Erichthonios 将第 $x$ 个方块的属性复制给第 $y$ 个方块及其所有与第 $y$ 个方块相邻、属性相同且连续的方块。（一个包含第 $y$ 个方块的相同属性方块段，且该段左侧相邻的方块属性不同或已超出边界，右侧同理。）
• $3\ x\ v$：Erichthonios 使所有与第 $x$ 个方块属性相同的方块的权重增加 $v$。
• $4\ x$：Erichthonios 攻击防御系统。只有输出第 $x$ 个方块的权重，你才能防御住这次攻击。

注意：由于你不知道 Erichthonios 下一步会做什么，查询经过了加密。（见输入格式）

如果你解决不了这个问题，以后会被 Hythlodaeus 取笑的。你不想那样，对吧？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数量 $T$ ($1 \le T \le 20$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 10^8, 1 \le q \le 10^5$)，分别表示 Themis 防御系统的方块数量和 Erichthonios 将执行的攻击次数。

接下来的 $q$ 行包含 Erichthonios 的攻击（初始时，$last = 0$）：

• $1\ x'\ c'$：包含 3 个整数，$1 \le x' \le n, 1 \le c' \le \lfloor \frac{n-1}{2} \rfloor$，实际的 $x = ((x' - 1) \oplus last) \pmod n + 1$，$c = ((c' - 1) \oplus last) \pmod {\lfloor \frac{n-1}{2} \rfloor} + 1$。
• $2\ x'\ y'$：包含 3 个整数，$1 \le x' \le n, 1 \le y' \le n$，实际的 $x = ((x' - 1) \oplus last) \pmod n + 1$，$y = ((y' - 1) \oplus last) \pmod n + 1$。
• $3\ x'\ v$：包含 3 个整数，$1 \le x' \le n, 1 \le v \le 10^9$，实际的 $x = ((x' - 1) \oplus last) \pmod n + 1$，且 $v$ 没有加密，$1 \le v \le 10^9$。
• $4\ x'$：包含 2 个整数，$1 \le x' \le n$，实际的 $x = ((x' - 1) \oplus last) \pmod n + 1$，在你得到 $Answer$ 后，别忘了更新 $last = Answer \ \& \ 1\,073\,741\,823$。

其中 $\oplus$ 表示按位异或运算，$\&$ 表示按位与运算。

保证 $n$ 的总和不超过 $2 \cdot 10^9$，且 $m$（即 $q$）的总和不超过 $10^6$。

输出格式

对于每个测试用例： 对于每次第 4 类攻击，输出一行一个整数，即该方块的权重。

样例

样例输入 1

1
16 12
3 10 16
4 2
1 1 6
1 5 6
1 9 7
1 15 7
2 2 10
2 2 13
3 1 16
4 16
4 9
4 4

样例输出 1

16
32
32
16

说明

样例中解码后的攻击如下：

$3, x = 10, v = 16$ $4, x = 2$ $1, x = 1, c = 1$ $1, x = 5, c = 1$ $1, x = 9, c = 2$ $1, x = 15, c = 2$ $2, x = 2, y = 10$ $2, x = 2, y = 13$ $3, x = 1, v = 16$ $4, x = 16$ $4, x = 9$ $4, x = 4$