$N$ 個の頂点からなる森がある。頂点には 1 から $N$ までの番号が付けられている。初期状態では辺はない。

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

• 1 u v: 2 頂点 $u$, $v$ を結ぶ辺を森に追加せよ。このクエリが呼ばれる以前に、森上で $u$ と $v$ を結ぶ経路がないことが保証される。
• 2 u k: $dist(u, v)$ を 2 頂点 $u, v$ 間の最短経路の長さと定義する。もし 2 頂点が連結でなければ、値は $\infty$ である。$dist(u, v) = k$ である頂点 $v$ の個数を返せ。

入力

最初の行に 2 つの整数 $N, Q$ が与えられる。($1 \le N \le 100\,000, 1 \le Q \le 200\,000$)

その後 $Q$ 行に 3 つの整数でクエリの情報 $t_i, a_i, b_i$ が与えられる。($1 \le t_i \le 2, 0 \le a_i, b_i < n$)

$last$ という追加の変数を考える。この変数は最初に 0 の値を持つ。

• $t_i = 1$ の場合、クエリの引数 $u_i, v_i$ は次のように定義される: $u_i = ((a_i + last) \bmod n) + 1, v_i = ((b_i + last) \bmod n) + 1$
• $t_i = 2$ の場合、クエリの引数 $u_i, k_i$ は次のように定義される: $u_i = ((a_i + last) \bmod n) + 1, k_i = ((b_i + last) \bmod n)$ このクエリに対する答えを計算した後、$last$ をそのクエリの答えで更新する。

出力

$t_i = 2$ の形式のクエリの答えを 1 行ずつ出力する。

入出力例

入力 1

7 9
1 0 6
1 4 3
1 0 5
1 1 2
1 3 1
1 4 5
2 2 3
2 2 1
2 0 0

出力 1

1
2
1