Olkoon $X = (x_1, x_2, \ldots, x_{n-1})$ mikä tahansa pituutta $n - 1$ oleva kokonaislukujono, jonka alkiot ovat välillä $1$ ja $n$, päätepisteet mukaan lukien. Tarkastellaan kaikkia puita, jotka täyttävät seuraavan ehdon. Ainakin yksi tällainen puu on aina olemassa. Määritellään $f(X)$ suurimmaksi halkaisijaksi näiden puiden joukossa.

• Puu koostuu $n$ solmusta, jotka on numeroitu $1$:stä $n$:ään. Kaaret on numeroitu $1$:stä $n - 1$:een. Jokaisella $i$ ($1 \le i \le n - 1$) toinen kaaren $i$ päätepisteistä on $x_i$.

Tässä puun halkaisija tarkoittaa suurinta kaarten määrää kahden solmun välisellä polulla.

Sinulle annetaan kaksi kokonaislukujonoa, $A = (a_1, a_2, \ldots, a_{n-1})$ ja $B = (b_1, b_2, \ldots, b_{n-1})$. Jokainen jonon $A$ alkio on välillä $1$ ja $n$, päätepisteet mukaan lukien. Jokainen jonon $B$ alkio on positiivinen. Voit olettaa, että parit $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ ovat keskenään erisuuria.

Ratkaise jokaiselle $d = 2, 3, \ldots, n - 1$ seuraava tehtävä:

Valitse kokonaislukujono $X = (x_1, x_2, \ldots, x_{n-1})$, jonka alkiot ovat välillä $1$ ja $n$, päätepisteet mukaan lukien, ja joka toteuttaa ehdon $f(X) = d$. Tällainen jono on aina olemassa. Jokaisella $i$ ($1 \le i \le n - 1$) maksat kustannuksen $2^{b_i}$ jos ja vain jos $x_i \ne a_i$. Etsi pienin mahdollinen kokonaiskustannus.

Koska kukin vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Syöte

Syöte koostuu yhdestä testitapauksesta seuraavassa muodossa.

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

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($3 \le n \le 2 \times 10^5$). Toinen rivi sisältää $n - 1$ kokonaislukua jonossa $A$ ($1 \le a_i \le n$). Kolmas rivi sisältää $n - 1$ kokonaislukua jonossa $B$ ($1 \le b_i \le 10^9$). On taattua, että $(a_i, b_i) \ne (a_j, b_j)$, jos $i \ne j$.

Tuloste

Tulosta $n - 2$ riviä. $k$:nnen rivin tulee sisältää vastaus arvolle $d = k + 1$, eli pienin mahdollinen kokonaiskustannus jonolle $X$, jolla $f(X) = k + 1$, modulo $998\,244\,353$.

Esimerkit

Syöte 1

5
2 4 3 4
1 2 4 8

Tuloste 1

18
2
0

Syöte 2

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

Tuloste 2

454
196
68
36
4
2
0
2

Syöte 3

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

Tuloste 3

0
16777216
150994944
226492415
830472183
671088562
394263947