$N$個の頂点からなる森がある。頂点には $1$ から $N$ までの番号が付けられており、辺は存在しない。すべての頂点 $v$ は整数 $X_v$ を持ち、初期値は $X_v = 1$ である。

以下のクエリを実行するプログラムを作成せよ。

• 1 $a$ $b$ $c$: 頂点 $a$ と $b$ を重み $c$ の辺で結ぶ。クエリの実行結果が森となる場合のみ入力で与えられる。
• 2 $a$ $b$: 頂点 $a$ と $b$ を結ぶ辺を削除する。2頂点の間に辺が存在する場合のみ入力で与えられる。
• 3 $a$: $X_a$ を $1-X_a$ に変更する。その後、$a$ が含まれる木において以下を求める。
  • 木の頂点を $v_1, v_2, \dots, v_k$ とする。このとき $\displaystyle \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$ が与えられる。2行目から $Q$ 行にわたって、クエリが1行に1つずつ与えられる。

入力で与えられるクエリの頂点番号（1, 2番クエリの $a$, $b$、3番クエリの $a$）は暗号化されており、クエリを実行する前に復号する必要がある。入力で与えられた頂点番号を $x$、直前の3番クエリで求めた値を $S$ としたとき、復号後の頂点番号は $(x-1+S) \bmod n + 1$ である。

出力

3番クエリで求めた値を、クエリが与えられた順に1行に1つずつ出力する。

制約

• $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