בממלכת 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