Нехай $X = (x_1, x_2, \ldots, x_{n-1})$ — довільна цілочисельна послідовність довжини $n - 1$, елементи якої лежать у межах від $1$ до $n$ включно. Розглянемо всі дерева, що задовольняють наступну умову. Принаймні одне таке дерево завжди існує. Визначимо $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$ розв'яжіть таку задачу:

Виберіть цілочисельну послідовність $X = (x_1, x_2, \ldots, x_{n-1})$, елементи якої лежать від $1$ до $n$ включно і яка задовольняє умову $f(X) = d$. Така послідовність завжди існує. Для кожного $i$ ($1 \le i \le n - 1$) ви сплачуєте вартість $2^{b_i}$ тоді й лише тоді, коли $x_i \ne a_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$). Другий рядок містить $n - 1$ цілих чисел послідовності $A$ ($1 \le a_i \le n$). Третій рядок містить $n - 1$ цілих чисел послідовності $B$ ($1 \le b_i \le 10^9$). Гарантується, що $(a_i, b_i) \ne (a_j, b_j)$, якщо $i \ne j$.

Вихідні дані

Виведіть $n - 2$ рядків. У $k$-му рядку має міститися відповідь для $d = k + 1$, тобто мінімально можлива сумарна вартість для послідовності $X$ такої, що $f(X) = k + 1$, за модулем $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