트리 경로 합성의 합

다음이 주어진다.

• $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 ))$ 을 정의하자.

각 정점 $x$에 대해 $q _ x = \sum _ {y=0} ^ {N-1} P(x, y)$을 $998244353$로 나눈 나머지를 구한다.

제약 조건

• 모든 입력은 정수이다.
• $1 \leq N \leq 200000$
• $0 \leq u _ i, v _ i \leq N - 1$
• $0 \leq a _ i \lt 998244353$
• $1 \leq b _ i \lt 998244353$
• $0 \leq c _ i \lt 998244353$

$N$
$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}$

$q _ 0$ $q _ 1$ $\ldots$ $q _ {N-1}$