問題文

$N$ 頂点 $0$ 辺の重み付き無向グラフ $G$ と 変数 $X$ があります。グラフの頂点にはそれぞれ $0$ から $N-1$ までの番号付けがされています。
変数 $X$ ははじめ $X_{0}$で初期化されています。
グラフ $G$ における2頂点間 $u$, $v$ の距離 ${\rm dist} (u, v)$ を次のように定義します。
$${\rm dist} (u, v) = 頂点\ u\ から頂点\ v\ への単純パスに含まれる辺すべての重みの総和$$ 同一頂点での距離は ${\rm dist}(v, v) = 0$ とします。
以下のような $Q$ 個のクエリが与えられるので、グラフ $G$ と変数 $X$ に対して順に処理してください。

• 1 v w：頂点 $v$ と頂点 $X$ を重み $w$ の辺で結ぶ。与えられる入力ではこの操作によってグラフ $G$ に閉路ができないことが保証される。
• 2 u v：頂点 $u$ と頂点 $v$ が連結でない場合-1を出力する。連結である場合、${\rm dist} (u, v)$ を出力し、 $X$ に ${\rm dist} (u, v)$ を加算する。
  その後、$X$ を $N$ で割ったあまりとする。
• 3 v：頂点 $v$ と同一の連結成分に含まれるすべての頂点対についての距離の最大値を出力する。(つまり頂点 $v$ が含まれる木の直径を出力する。)
  頂点 $v$ と連結である頂点が $1$ つしかない (頂点 $v$ のみである) 場合、0 を出力する。
• 4 value：$X$ に値 ${\rm value}$ を加算する。その後、$X$ を $N$ で割ったあまりとする。

入力

$N\ X_{0}\ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq Q \leq 3 \times 10^{5}$
• $0 \leq X_{0} < N$
• ${\rm Query}_{i}$について
  
  タイプ1のクエリのとき

  $1\ v_{i}\ w_{i}$

  タイプ2のクエリのとき

  $2\ u_{i}\ v_{i}$

  タイプ3のクエリのとき

  $3\ v_{i}$

  タイプ4のクエリのとき

  $4\ {\rm value}_{i}$

  ・$0 \leq u_{i}, v_{i}, {\rm value}_{i} < N$
  ・$0 \leq w_{i} \leq 10^{9}$
  ・タイプ1のクエリによってグラフ $G$ に閉路ができないことが保証される。


• 入力はすべて整数

出力

タイプ2、タイプ3のクエリが合計で $K$ 個与えられるとして、 $i\ (1 \leq i \leq K)$ 行目にそれぞれのクエリの回答を1行に出力してください。最後に改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

5 1 10
1 0 1
2 0 1
1 3 5
1 1 3
3 0
1 4 6
2 4 0
2 4 3
2 3 1
3 3

出力

1
9
10
11
8
11

サンプル1の説明を見る (クリックで展開します)

初期状態は $N$ 頂点 $0$ 辺となっていて変数は $X = 1$ に初期化されています。

• 1 0 1：1つ目のクエリでは、頂点 $0$ と頂点 $X = 1$ を重み $1$ の辺で結びます。(b)
• 2 0 1：2つ目のクエリでは、${\rm dist}(0, 1) = 1$ を出力します。これにより変数は $X = 1 + 1 = 2$ となります。(c)
• 1 3 5：3つ目のクエリでは、頂点 $3$ と頂点 $X = 2$ を重み $5$ の辺で結びます。(d)
• 1 1 3：4つ目のクエリでは、頂点 $1$ と頂点 $X = 2$ を重み $3$ の辺で結びます。(d)
• 3 0：5つ目のクエリでは、頂点 $0$ が所属している連結成分の木の直径を出力します。これは ${\rm dist}(0, 3) = 9$ です。
• 1 4 6：6つ目のクエリでは、頂点 $4$ と頂点 $X = 2$ を重み $6$ の辺で結びます。(e)
• 2 4 0：7つ目のクエリでは、${\rm dist}(4, 0) = 10$ を出力します。これにより変数は $X = (2 + 10) \bmod\ 5 = 1$ となります。(f)
• 2 4 3：8つ目のクエリでは、${\rm dist}(4, 3) = 11$ を出力します。これにより変数は $X = (2 + 11) \bmod\ 5 = 3$ となります。(g)
• 2 3 1：9つ目のクエリでは、${\rm dist}(3, 1) = 8$ を出力します。これにより変数は $X = (3 + 8) \bmod\ 5 = 1$ となります。(h)
• 3 3：10個目のクエリでは、頂点 $3$ が所属している連結成分の木の直径を出力します。これは ${\rm dist}(3, 4) = 11$ です。

200000 0 9
2 0 1
1 1 1000000000
4 1
1 2 1000000000
4 1
1 3 1000000000
4 1
1 4 1000000000
3 1

-1
4000000000

200000 0 8
1 1 3
2 0 1
1 2 5
2 2 3
2 3 2
1 1 40
1 2 40
2 3 0

3
5
5
88

200000 1 12
1 0 1000000000
1 2 1000000000
4 2
1 2 1000000000
1 4 1000000000
4 2
1 4 1000000000
1 6 1000000000
2 0 6
4 2
1 6 1000000000
2 0 7

6000000000
7000000000