$X = (x_1, x_2, \ldots, x_{n-1})$를 각 원소가 $1$ 이상 $n$ 이하인 길이 $n - 1$의 임의의 정수열이라고 하자. 다음 조건을 만족하는 모든 트리를 생각하자. 이러한 트리는 항상 적어도 하나 존재한다. 이 트리들 중 지름의 최댓값을 $f(X)$로 정의한다.

• 트리는 $n$개의 정점으로 이루어져 있으며, 정점에는 $1$부터 $n$까지 번호가 매겨져 있다. 간선에는 $1$부터 $n - 1$까지 번호가 매겨져 있다. 각 $i$ ($1 \le i \le n - 1$)에 대하여, 간선 $i$의 양 끝점 중 하나는 $x_i$이다.

여기서 트리의 지름이란 두 정점 사이의 경로에 포함되는 간선 개수의 최댓값을 의미한다.

두 정수열 $A = (a_1, a_2, \ldots, a_{n-1})$와 $B = (b_1, b_2, \ldots, b_{n-1})$가 주어진다. $A$의 각 원소는 $1$ 이상 $n$ 이하이다. $B$의 각 원소는 양수이다. 순서쌍 $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$는 모두 서로 다르다고 가정해도 좋다.

각 $d = 2, 3, \ldots, n - 1$에 대하여 다음 문제를 해결하시오:

각 원소가 $1$ 이상 $n$ 이하이고 $f(X) = d$를 만족하는 정수열 $X = (x_1, x_2, \ldots, x_{n-1})$를 선택한다. 이러한 수열은 항상 존재한다. 각 $i$ ($1 \le i \le n - 1$)에 대하여, $x_i \ne a_i$일 때 그리고 그때에만 $2^{b_i}$의 비용을 지불한다. 가능한 총비용의 최솟값을 구하시오.

각 답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하시오.

입력

입력은 다음과 같은 형식의 단일 테스트 케이스로 주어진다.

$$ \begin{aligned} &n \\ &a_1 \ a_2 \ \cdots \ a_{n-1} \\ &b_1 \ b_2 \ \cdots \ b_{n-1} \end{aligned} $$

첫째 줄에 정수 $n$ ($3 \le n \le 2 \times 10^5$)이 주어진다. 둘째 줄에 수열 $A$의 $n - 1$개의 정수 ($1 \le a_i \le n$)가 주어진다. 셋째 줄에 수열 $B$의 $n - 1$개의 정수 ($1 \le b_i \le 10^9$)가 주어진다. $i \ne j$이면 $(a_i, b_i) \ne (a_j, b_j)$임이 보장된다.

출력

$n - 2$개의 줄을 출력한다. $k$번째 줄에는 $d = k + 1$에 대한 답, 즉 $f(X) = k + 1$을 만족하는 수열 $X$의 가능한 최소 총비용을 $998\,244\,353$으로 나눈 나머지를 출력해야 한다.

예제

입력 1

5
2 4 3 4
1 2 4 8

출력 1

18
2
0

입력 2

10
6 2 1 6 10 4 6 10 4
1 1 7 8 1 5 5 5 10

출력 2

454
196
68
36
4
2
0
2

입력 3

9
1 1 1 1 1 1 1 1
24 27 30 33 36 39 42 45

출력 3

0
16777216
150994944
226492415
830472183
671088562
394263947