AT_scpc2026_div1_l Lulu, the Magician

#### 表示言語 / / ルルは実は天才魔法使いである．ルルは長い研究の末，魔法陣を活用した自分だけの秘伝の魔法を開発した． ルルが扱う魔法陣は， $ N $ 個の魔法と $ N-1 $ 個の接続関係からなる木構造である．各魔法には $ 1 $ から $ N $ まで順に番号が付いており，ルルはそれらを強化できる．魔法陣の $ i $ 番目の接続関係は，魔法 $ a_i $ と魔法 $ b_i $ が互いに直接つながっていることを意味する． 最初，すべての魔法の威力は $ 0 $ である．ルルが魔法 $ r $ を $ w $ だけ強化すると， $ r $ の威力 $ W_r $ が $ w $ だけ増加する． ルルは魔法陣の $ 2 $ つの魔法 $ u $ と $ v $ を選んで魔法を詠唱できる．ルルが魔法を詠唱すると，魔法陣にあるすべての魔法が， $ u $ と $ v $ を結ぶ唯一の単純パス上にある頂点の集合 $ P(u,v) $ と相互作用する．ルルが詠唱した魔法の最終威力は次の式で計算できる．ここで， $ d(a,b) $ は $ a $ と $ b $ を結ぶ唯一の単純パス上にある辺の本数である． $ \sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x) $ 天才魔法使いルルは，次の $ 2 $ 種類の行動を順に $ Q $ 回行いながら，魔法を身につけようとしている． - `1 v w`: 魔法 $ v $ の威力を $ w $ だけ増加させる． - `2 u v`: 魔法 $ u $ と魔法 $ v $ を選んで魔法を詠唱する． タイプ $ 2 $ の行動を行うたびに，詠唱した魔法の最終威力を $ 998\,244\,353 $ で割った余りを計算しよう．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ \mathrm{action}_1 $ $ \mathrm{action}_2 $ $ \vdots $ $ \mathrm{action}_Q $

タイプ $ 2 $ の行動を行うたびに，詠唱した魔法の最終威力を $ 998\,244\,353 $ で割った余りを $ 1 $ 行に出力せよ．

### Constraints - $ 1 \leq N, Q \leq 200\,000 $ - $ 1 \leq a_i, b_i \leq N $ - $ a_i \ne b_i $ - 与えられる魔法陣は木構造である． - `1 v w` の形式の行動では， $ 1 \leq v \leq N $ かつ $ 1 \leq w \leq 10^9 $ である． - `2 u v` の形式の行動では， $ 1 \leq u, v \leq N $ である． - 入力される数値はすべて整数である．