H Tree Queries

問題文

umgくんは、 $N$ 頂点の木を持っています。頂点 $i \ (1\leq i \leq N)$ の重みは $v_i$ です。 $j \ (1 \leq j \leq N-1)$ 番目の辺は、頂点 $a_i$ と頂点 $b_i$ を結び、その重みは $w_i$ です。さらに、木全体の重みを「 $\sum_{1\leq a \lt b \leq N} \mathrm{dist}(a,b) v_a v_b$ を $998244353$ で割った余り」で定めます。 (15:05 更新) ここで、 $\mathrm{dist}(a,b)$ というのは、頂点 $a$ から頂点 $b$ の最短経路上に存在する辺の重みの和を表しています。

umgくんはまず、今持っている木全体の重みを知りたいです。さらに、 $Q$ 個の変更クエリが与えられます。クエリの種類は以下の2つです。

1. 頂点クエリ : 頂点 $c \ (1\leq c \leq N)$ の重みを $x$ 増やす。その後、現在の木全体の重みを出力する。
2. 辺クエリ : 辺 $e \ (1\leq e \leq N-1)$ の重みを $x$ 増やす。その後、現在の木全体の重みを出力する。

これらのクエリを処理してください。

入力

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

$N$
$v_1$ $v_2$ $\cdots$ $v_N$
$a_1$ $b_1$ $w_1$
$a_2$ $b_2$ $w_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$ $w_{N-1}$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

$query_i$の入力形式は以下の2つのいずれかである。

• 頂点クエリ

$1$ $c$ $x$

• 辺クエリ

$2$ $e$ $x$

制約

• 入力はすべて整数である。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq v_i \leq 10^8 \ (1\leq i \leq N)$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i,b_i \leq N$
• $1 \leq w_i \leq 10^8 \ (1\leq i \leq N-1)$
• 与えられるグラフは木である。
• クエリ1の$c$は$1\leq c \leq N$を満たす。
• クエリ2の$e$は$1\leq e \leq N-1$を満たす。
• クエリ1,2の$x$は$1\leq x \leq 10^8$を満たす。
• クエリ1の数は20000以下である。

出力

答えを $Q+1$ 行に出力せよ。$1$行目には木の最初の状態で木全体の重み、$i+1$行目には、$i$番目の変更クエリ後の木全体の重みを出力せよ。

入力例1

3
1 2 4
1 2 1
2 3 2
2
1 1 1
2 2 2

出力例1

30
44
76

例えば、木の最初の状態の木全体の重みは、 $\mathrm{dist}(1,2) \times 1 \times 2 + \mathrm{dist}(1,3) \times 1 \times 4 + \mathrm{dist}(2,3) \times 2 \times 4 = 2+12+16=30$ です。

入力例2

4
2 2 3 3
1 2 4
1 3 3
1 4 1
3
2 3 4
1 4 1
2 1 10

出力例2

148
232
284
464

---