ليكن $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