ให้ $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