תהי $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