정점 설정 및 경로 함수 합성

$N$개의 정점을 가진 트리가 주어진다. 간선은 $(u_i, v_i)$이고, 각 $i$에 대해 정점 $i$에 일차 함수 $f_i(x) = a_i x + b_i$가 쓰여 있다. $Q$개의 쿼리를 다음과 같이 처리한다:

• 0 $p$ $c$ $d$: $f_p \gets cx + d$로 설정한다.
• 1 $u$ $v$ $x$: $u$와 $v$ 사이의 경로 위 정점들을 $p_1 = u, p_2, ..., p_k = v$라 하자. $f_{p_k}(...f_{p_2}(f_{p_1}(x))) \bmod 998244353$를 출력한다.

제약 조건

• $1 \leq N, Q \leq 200000$
• $1 \leq a_i, c < 998244353$
• $0 \leq b_i, d, x < 998244353$
• $0 \leq p < N$
• $0 \leq u, v < N$

$N$ $Q$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{N - 1}$ $b_{N - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{N - 2}$ $v_{N - 2}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

1 $u$ $v$ $x$: $u$와 $v$ 사이의 경로 위 정점들을 $p_1 = u, p_2, ..., p_k = v$라 하자. $f_{p_k}(...f_{p_2}(f_{p_1}(x))) \bmod 998244353$를 출력한다.