อาณาจักร JOI มีเมือง $N$ เมือง หมายเลข $1$ ถึง $N$ เมือง $1$ เป็นเมืองหลวง แต่ละเมืองมีค่าที่เรียกว่า ความคึกคัก โดยค่าความคึกคักเริ่มต้นของเมือง $i$ ($1 \le i \le N$) คือ $C_i$

ถนนในอาณาจักร JOI เชื่อมเมืองสองเมืองที่แตกต่างกันและเดินทางได้ทั้งสองทิศทาง ในตอนแรก อาณาจักร JOI ไม่มีถนนเลย คุณวางแผนก่อสร้างถนน $N-1$ ครั้ง โดยการก่อสร้างครั้งที่ $j$ ($1 \le j \le N-1$) มีแผนดังนี้

• กำหนดเมืองสองเมือง $A_j$ และ $B_j$ โดยเมื่อใช้เฉพาะถนนที่สร้างแล้วในขณะนั้น จะเดินทางจากเมือง $1$ ไปยังเมือง $A_j$ ได้ แต่เดินทางจากเมือง $1$ ไปยังเมือง $B_j$ ไม่ได้

• สร้างถนนเชื่อมเมือง $A_j$ กับเมือง $B_j$ ค่าใช้จ่ายในการก่อสร้างครั้งนี้คือจำนวนคู่เมือง $(s,t)$ ที่เป็นไปตามเงื่อนไขต่อไปนี้:

  เมือง $s$ และเมือง $t$ อยู่บนเส้นทางที่สั้นที่สุดระหว่างเมือง $1$ กับเมือง $A_j$ และเมื่อเดินทางจากเมือง $1$ ไปยังเมือง $A_j$ จะถึงเมือง $s$ ก่อนเมือง $t$ อีกทั้งค่าความคึกคักของเมือง $s$ ต้องมากกว่าค่าของเมือง $t$ อย่างเคร่งครัด

  ในที่นี้ เมืองบนเส้นทางระหว่างเมือง $1$ กับเมือง $A_j$ รวมเมือง $1$ และเมือง $A_j$ ด้วย โปรดสังเกตว่าเส้นทางที่สั้นที่สุดระหว่างเมือง $1$ กับเมือง $A_j$ มีเพียงเส้นทางเดียว

• ค่าความคึกคักของทุกเมืองบนเส้นทางระหว่างเมือง $1$ กับเมือง $A_j$ เปลี่ยนเป็นค่าความคึกคักของเมือง $B_j$

คุณต้องการทราบค่าใช้จ่ายในการก่อสร้างแต่ละครั้ง

งานที่ต้องทำ

จงเขียนโปรแกรมที่รับข้อมูลเมืองและการก่อสร้างถนน แล้วคำนวณค่าใช้จ่ายในการก่อสร้างแต่ละครั้ง

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N$ ซึ่งหมายความว่าอาณาจักร JOI มีเมือง $N$ เมือง
• บรรทัดที่สองมีจำนวนเต็ม $N$ จำนวน $C_1,C_2,\ldots,C_N$ คั่นด้วยช่องว่าง ซึ่งหมายความว่าค่าความคึกคักเริ่มต้นของเมือง $i$ ($1 \le i \le N$) คือ $C_i$
• บรรทัดที่ $j$ ($1 \le j \le N-1$) ของ $N-1$ บรรทัดถัดไปมีจำนวนเต็มสองจำนวน $A_j,B_j$ คั่นด้วยช่องว่าง ซึ่งหมายความว่าเมือง $A_j$ และเมือง $B_j$ ถูกกำหนดไว้สำหรับการก่อสร้างถนนครั้งที่ $j$

ข้อมูลส่งออก

เขียน $N-1$ บรรทัดลงในข้อมูลส่งออกมาตรฐาน บรรทัดที่ $j$ ($1 \le j \le N-1$) มีค่าใช้จ่ายในการก่อสร้างถนนครั้งที่ $j$

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $1 \le N \le 100\,000$
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le A_j \le N$ ($1 \le j \le N-1$)
• $1 \le B_j \le N$ ($1 \le j \le N-1$)
• เมื่อใช้ถนนที่สร้างก่อนการก่อสร้างครั้งที่ $j$ จะเดินทางจากเมือง $1$ ไปยังเมือง $A_j$ ได้ แต่เดินทางจากเมือง $1$ ไปยังเมือง $B_j$ ไม่ได้ ($1 \le j \le N-1$)

งานย่อย

มีงานย่อย 3 งาน คะแนนและข้อจำกัดเพิ่มเติมของแต่ละงานย่อยเป็นดังนี้:

งานย่อย 1 [7 คะแนน]

• $N \le 500$

งานย่อย 2 [9 คะแนน]

• $N \le 4000$

งานย่อย 3 [84 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

ข้อมูลส่งออก 1

0
0
0
2

หมายเหตุ

ในข้อมูลนำเข้าตัวอย่างที่ 1 การก่อสร้างดำเนินไปดังนี้:

• ในการก่อสร้างครั้งแรก ไม่มีคู่ $(s,t)$ ที่เป็นไปตามเงื่อนไข ค่าใช้จ่ายจึงเป็น $0$ สร้างถนนเชื่อมเมือง $1$ กับเมือง $2$ และค่าความคึกคักของเมือง $1$ เปลี่ยนเป็น $2$
• ในการก่อสร้างครั้งที่สอง ไม่มีคู่ $(s,t)$ ที่เป็นไปตามเงื่อนไขเช่นกัน ค่าใช้จ่ายจึงเป็น $0$ สร้างถนนเชื่อมเมือง $2$ กับเมือง $3$ และค่าความคึกคักของเมือง $1$ และเมือง $2$ เปลี่ยนเป็น $3$
• ในการก่อสร้างครั้งที่สาม ไม่มีคู่ $(s,t)$ ที่เป็นไปตามเงื่อนไขเช่นกัน ค่าใช้จ่ายจึงเป็น $0$ สร้างถนนเชื่อมเมือง $2$ กับเมือง $4$ และค่าความคึกคักของเมือง $1$ และเมือง $2$ เปลี่ยนเป็น $4$
• ในการก่อสร้างครั้งที่สี่ คู่สองคู่ $(s,t)=(1,3),(2,3)$ เป็นไปตามเงื่อนไข ค่าใช้จ่ายจึงเป็น $2$ สร้างถนนเชื่อมเมือง $3$ กับเมือง $5$ และค่าความคึกคักของเมือง $1$, เมือง $2$ และเมือง $3$ เปลี่ยนเป็น $5$

ข้อมูลนำเข้า 2

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

ข้อมูลส่งออก 2

0
0
0
1
1
0
1
2
3