Пусть $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