問題文

$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 XOR} $$ 同一頂点での距離は ${\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$ と同一の連結成分に含まれるすべての頂点対についての距離の総和を $998244353$ で割ったあまりを出力する。
  すなわち、頂点 $v$ と連結である頂点 (頂点 $v$ も含む)が $K$ 個あるとし、それぞれ $ u = (u_{1}, u_{2}, u_{3}, \cdots, u_{K})$ とした際の $$ \left( \sum_{i=2}^{K}\sum_{j=1}^{i-1} {\rm dist}(u_{i}, u_{j}) \right) \bmod\ 998244353 $$ を出力する。頂点 $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} < 2^{30}$
  ・タイプ1のクエリによってグラフ $G$ に閉路ができないことが保証される。


• 入力はすべて整数

出力

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

サンプル

サンプル1

入力

5 1 11
1 0 1
2 0 1
2 0 2
1 0 2
3 1
4 4
1 3 5
3 3
2 3 2
1 4 11
3 3

出力

1
-1
6
21
6
62

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

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

• 1 0 1：1つ目のクエリでは、頂点 $0$ と頂点 $X = 1$ を重み $1$ の辺で結びます。
• 2 0 1：2つ目のクエリでは、頂点 $0$ と頂点 $1$ の距離 ${\rm dist}(0, 1) = 1$ を出力します。変数 $X$ に $1$ を加算し、$5$ で割ったあまりとします。これによって変数 $X$ は $2$ となります。
• 2 0 2：3つ目のクエリでは、頂点 $0$ と頂点 $2$ は非連結ですので、$-1$ を出力します
• 1 0 2：4つ目のクエリでは、頂点 $0$ と頂点 $X = 2$ を重み $2$ の辺で結びます。
• 3 1：5つ目のクエリでは、頂点 $1$ の所属する連結成分についての頂点対の距離の総和が求められます。
  ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(1,2) = 3$ですので、これらの総和である $6$ を出力します。
• 4 4：6つ目のクエリでは、変数 $X$ に $4$ を加算し、 $5$ で割った余りとします。これによって変数 $X$ は $1$ となります。
• 1 3 5：7つ目のクエリでは、頂点 $3$ と頂点 $X = 1$ を重み $5$ の辺で結びます。
• 3 3：8つ目のクエリでは、頂点 $3$ の所属する連結成分についての頂点対の距離の総和が求められます。
  ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(0,3) = 4, {\rm dist}(1,2) = 3, {\rm dist}(1,3) = 5, {\rm dist}(2, 3) = 6$ ですので、これらの総和である $21$ を出力します。
• 2 3 2：9つ目のクエリでは、頂点 $3$ と頂点 $2$ の距離 ${\rm dist}(3, 2) = 6$ を出力します。変数 $X$ に $6$ を加算し、$5$ で割ったあまりとします。これによって変数 $X$ は $2$ となります。
• 1 4 11：10個目のクエリでは、頂点 $4$ と頂点 $X = 2$ を重み $11$ の辺で結びます。
• 3 3：11個目のクエリでは、頂点 $3$ の所属する連結成分についての頂点対の距離の総和が求められます。
  ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(0,3) = 4, {\rm dist}(0,4) = 9,{\rm dist}(1,2) = 3, {\rm dist}(1,3) = 5, {\rm dist}(1,4) = 8, {\rm dist}(2, 3) = 6,$
  ${\rm dist}(2, 4) = 11, {\rm dist}(3, 4) = 13$ ですので、これらの総和である $62$ を出力します。

7 5 15
2 0 5
1 1 542099847
1 0 126014135
2 6 1
1 3 606571677
1 4 630122460
3 2
2 5 3
2 6 6
1 2 660183552
3 3
2 1 3
2 5 1
2 5 2
3 1

-1
-1
0
606571677
0
995222351
73942298
542099847
58594973
995222351

8 3 10
2 6 2
1 1 789992496
1 4 345094264
1 2 654214606
1 5 184875134
3 1
1 7 378850180
1 0 389600407
3 0
2 2 3

-1
900591855
327463395
654214606