동적 트리 정점 설정 경로 합성

정점이 $N$개인 트리가 주어진다. 간선은 $(u_i, v_i)$이며, 각 $i$에 대해 정점 $i$에는 일차 함수 $f_i(x) = a_i x + b_i$가 적혀 있다.

다음과 같이 $Q$개의 쿼리를 처리한다. 쿼리를 처리한 후에도 그래프는 트리로 유지된다.

• 0 $u$ $v$ $w$ $x$: 기존 간선 $(u, v)$을 제거하고 새 간선 $(w, x)$을 추가한다
• 1 $p$ $c$ $d$: $f_p \gets cx + d$으로 설정한다
• 2 $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}$

2 $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$을 출력한다