점 설정 트리 경로 합성 합

다음이 주어진다.

• $N$개의 정점을 가진 트리,
• $N$개의 정수 $a _ 0, a _ 1, \ldots, a _ {N-1}$ ,
• $N-1$개의 정수 $b _ 0, b _ 1, \ldots, b _ {N-2}$ , 그리고
• $N-1$개의 정수 $c _ 0, c _ 1, \ldots, c _ {N-2}$ .

간선 $i$은 정점 $u _ i$과 정점 $v _ i$을 양방향으로 연결한다.

$0 \leq e \leq N-2$을 만족하는 정수 $e$에 대해, $f _ e(x) = b _ e x + c _ e$라 하자.

정점 $x$에서 정점 $y$까지의 단순 경로에 있는 간선들을 순서대로 $e _ 0, e _ 1, \ldots, e _ k$라 하고, $P(x, y) = f _ {e _ 0}(f _ {e _ 1}(\ldots f _ {e _ k}(a _ y) \ldots ))$을 정의하자.

$Q$개의 쿼리를 주어진 순서대로 처리한다. 쿼리에는 두 가지 유형이 있다.

• 0 w x r : $a_w$을 $x$로 갱신한 다음 $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$을 출력한다.
• 1 e y z r : $(b_e, c_e)$을 $(y, z)$로 갱신한 다음 $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$을 출력한다.

제약 조건

• 모든 입력은 정수이다.
• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq u _ i, v _ i \leq N - 1$
• $0 \leq a _ w \lt 998244353$
• $1 \leq b _ e \lt 998244353$
• $0 \leq c _ e \lt 998244353$
• $0 \leq w \leq N - 1$
• $0 \leq e \leq N - 2$
• $0 \leq x \lt 998244353$
• $1 \leq y \lt 998244353$
• $0 \leq z \lt 998244353$
• $0 \leq r \leq N - 1$

$\mathrm{Query}_i$은 $i$번째 쿼리를 나타낸다.

$N$ $Q$
$a _ 0$ $a _ 1$ $\ldots$ $a _ {N-1}$
$u _ 0$ $v _ 0$ $b _ 0$ $c _ 0$
$u _ 1$ $v _ 1$ $b _ 1$ $c _ 1$
$\vdots$
$u _ {N-2}$ $v _ {N-2}$ $b _ {N-2}$ $c _ {N-2}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\vdots$
$\mathrm{Query}_{Q-1}$

$p_i$은 $i$번째 쿼리의 답을 나타낸다.

$p_0$
$p_1$ 
$\vdots$
$p_{Q-1}$