JOI патшалығында $1$-ден $N$-ге дейінгі сандармен нөмірленген $N$ қала бар. $1$-ші қала — астана. Әр қаланың жанданғандық деп аталатын мәні бар және $i$ қаласының ($1 \le i \le N$) бастапқы жанданғандық мәні $C_i$-ге тең.

JOI патшалығындағы жол екі түрлі қаланы екі бағытта байланыстырады. Бастапқыда JOI патшалығында ешқандай жол жоқ. Сіз $N-1$ жол құрылысын жоспарладыңыз. $j$-ші құрылысты ($1 \le j \le N-1$) келесі түрде жүргізу жоспарланған.

• Сол уақытта салынған жолдарды ғана пайдаланып, $1$ қаласынан $A_j$ қаласына баруға болатын және $1$ қаласынан $B_j$ қаласына баруға болмайтын екі қала — $A_j$ және $B_j$ таңдалады.

• Сіз $A_j$ қаласы мен $B_j$ қаласын байланыстыратын жол саласыз. Бұл құрылыстың құны келесі шарттарды қанағаттандыратын $(s,t)$ қалалар жұптарының санына тең:

  $s$ қаласы мен $t$ қаласы $1$ қаласы мен $A_j$ қаласының арасындағы ең қысқа жолдың бойында жатады, әрі $1$ қаласынан $A_j$ қаласына барғанда адам $t$ қаласынан бұрын $s$ қаласына жетеді және $s$ қаласының жанданғандық мәні $t$ қаласының жанданғандық мәнінен қатаң түрде үлкен болады.

  Мұнда $1$ қаласы мен $A_j$ қаласының арасындағы жолдың бойында жатқан қалаларға $1$ қаласы мен $A_j$ қаласы да кіреді. $1$ қаласы мен $A_j$ қаласының арасындағы ең қысқа жол жалғыз екеніне назар аударыңыз.

• $1$ қаласы мен $A_j$ қаласының арасындағы жолдың бойында жатқан барлық қалалардың жанданғандық мәндері $B_j$ қаласының жанданғандық мәніне өзгереді.

Сіз әрбір құрылыстың құнын білгіңіз келеді.

Тапсырма

Қалалар мен жол құрылыстары туралы деректер берілген. Әрбір құрылыстың құнын есептейтін бағдарлама жазыңыз.

Кіріс форматы

Стандартты кірістен келесі деректерді оқыңыз.

• Кірістің бірінші қатарында $N$ бүтін саны берілген. Бұл JOI патшалығында $N$ қала бар екенін білдіреді.
• Кірістің екінші қатарында бос орынмен бөлінген $N$ бүтін сан $C_1, C_2, \cdots C_N$ берілген. Бұл $i$ қаласының ($1 \le i \le N$) бастапқы жанданғандық мәні $C_i$ екенін білдіреді.
• Келесі $N-1$ қатардың $j$-ші қатарында ($1 \le j \le N-1$) бос орынмен бөлінген екі бүтін сан $A_j$, $B_j$ берілген. Бұл $j$-ші жол құрылысы үшін $A_j$ қаласы мен $B_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