問題文

$N$ 頂点の根付き木があります。根は頂点 $1$ です。木の $i$ 番目 ($1 \leq i \leq N-1$) の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。
木の各頂点には整数が書かれています。最初、頂点 $i$ には $X_i$ が書かれています。
以下の $4$ 種類のクエリが合計 $Q$ 個与えられるので、すべて処理してください。

• クエリ $1$: $X_V \bmod 998\,244\,353$ を求める。
• クエリ $2$: 頂点 $V$ からの距離が $K$ 以下であるそれぞれの頂点 $v$ に対し、$X_v$ を $CX_v+D$ で置き換える。
• クエリ $3$: 頂点 $V$ の部分木に含まれるそれぞれの頂点 $v$ に対し、$X_v$ を $CX_v+D$ で置き換える。
• クエリ $4$: 頂点 $U,V$ を結ぶ単純パスに含まれるそれぞれの頂点 $v$ に対し、$X_v$ を $CX_v+D$ で置き換える。

入力

入力は以下の形式で標準入力から与えられます。

$N\ Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$X_1$ $X_2$ $\cdots$ $X_N$
$\text{Query}_1$
$\text{Query}_2$
$\vdots$
$\text{Query}_Q$

• $i$ 番目のクエリがクエリ $1$ のとき:

  $1$ $V$

• $i$ 番目のクエリがクエリ $2$ のとき:

  $2$ $V$ $K$ $C$ $D$

• $i$ 番目のクエリがクエリ $3$ のとき:

  $3$ $V$ $C$ $D$

• $i$ 番目のクエリがクエリ $4$ のとき:

  $4$ $U$ $V$ $C$ $D$

出力

それぞれのクエリ $1$ に対し、答えを標準出力に $1$ 行で出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

• $2 \leq N \leq 100\,000$
• $1 \leq Q \leq 100\,000$
• $1 \leq A_i \leq N$ ($1 \leq i \leq N-1$)
• $1 \leq B_i \leq N$ ($1 \leq i \leq N-1$)
• 与えられるグラフは木である。
• $0 \leq X_i < 998\,244\,353$ ($1 \leq i \leq N$)
• $i$ 番目 ($1 \leq i \leq Q$) のクエリがクエリ $1$ のとき、
  • $1 \leq V \leq N$
• $i$ 番目 ($1 \leq i \leq Q$) のクエリがクエリ $2$ のとき、
  • $1 \leq V \leq N$
  • $K=1$
  • $1 \leq C < 998\,244\,353$
  • $0 \leq D < 998\,244\,353$
• $i$ 番目 ($1 \leq i \leq Q$) のクエリがクエリ $3$ のとき、
  • $1 \leq V \leq N$
  • $1 \leq C < 998\,244\,353$
  • $0 \leq D < 998\,244\,353$
• $i$ 番目 ($1 \leq i \leq Q$) のクエリがクエリ $4$ のとき、
  • $1 \leq U \leq N$
  • $1 \leq V \leq N$
  • $U \neq V$
  • $1 \leq C < 998\,244\,353$
  • $0 \leq D < 998\,244\,353$
• 入力される値はすべて整数である。

サンプル

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

123
134
235
134
134
235
235

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

123
12345
245
123
23
12
2