有一个由 $N$ 个顶点组成的森林。顶点编号为 $1$ 到 $N$，初始时没有边。每个顶点 $v$ 有一个整数 $X_v$，初始值为 $X_v = 1$。

编写一个程序执行以下查询：

• 1 $a$ $b$ $c$：用一条权重为 $c$ 的边连接顶点 $a$ 和 $b$。输入保证查询执行后结果仍为森林。
• 2 $a$ $b$：删除连接顶点 $a$ 和 $b$ 的边。输入保证这两个顶点之间确实存在一条边。
• 3 $a$：将 $X_a$ 修改为 $1-X_a$。然后，在包含 $a$ 的树中计算以下内容：
  • 设树的顶点为 $v_1, v_2, \dots, v_k$。计算 $\min_{1 \le i \le k}{\left\{ \sum_{1 \le j \le k}{dist(v_i, v_j) \times X_{v_j}} \right\}}$ 并输出。其中 $dist(v_i, v_j)$ 是从 $v_i$ 到 $v_j$ 路径上所有边的权重之和。

输入格式

第一行包含顶点数 $N$ 和查询数 $Q$。接下来 $Q$ 行，每行一个查询。

输入中给出的顶点编号（第 1、2 类查询中的 $a$、$b$，第 3 类查询中的 $a$）是加密的，需要在执行查询前解密。设输入的顶点编号为 $x$，上一次第 3 类查询得到的值为 $S$，则解密后的顶点编号为 $(x-1+S) \bmod {n} + 1$。

输出格式

对于每个第 3 类查询，按查询给出的顺序，每行输出一个计算得到的值。

数据范围

• $1 \le N \le 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le a, b \le N$
• $a \ne b$
• $1 \le c \le 10^8$

样例

输入格式 1

3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2

输出格式 1

4
0
0

输入格式 2

5 17
1 1 5 10
1 3 1 7
1 5 2 5
1 3 4 2
2 3 1
1 4 1 6
2 5 2
3 1
3 2
3 2
1 2 1 2
3 4
2 5 1
1 4 5 2
2 3 4
1 3 5 9
3 5

输出格式 2

18
2
0
0
9

输入格式 3

10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3

输出格式 3

274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409