JOI-kuningaskunnassa on $N$ kaupunkia, jotka on numeroitu luvuilla $1$:stä $N$:ään. Kaupunki $1$ on pääkaupunki. Jokaisella kaupungilla on arvo, jota kutsutaan eloisuudeksi, ja kaupungin $i$ ($1 \le i \le N$) eloisuuden alkuarvo on $C_i$.

Tie JOI-kuningaskunnassa yhdistää kaksi eri kaupunkia kaksisuuntaisesti. Aluksi JOI-kuningaskunnassa ei ole yhtään tietä. Olet suunnitellut $N-1$ tienrakennustyötä. $j$-s rakennustyö ($1 \le j \le N-1$) on suunniteltu tehtäväksi seuraavalla tavalla.

• Valitaan kaksi kaupunkia, $A_j$ ja $B_j$, kun kaupungista $1$ pääsee kaupunkiin $A_j$, mutta kaupungista $1$ ei pääse kaupunkiin $B_j$ käyttämällä vain siihen mennessä rakennettuja teitä.

• Rakennat tien, joka yhdistää kaupungin $A_j$ ja kaupungin $B_j$. Tämän rakennustyön kustannus on sellaisten kaupunkiparien $(s,t)$ lukumäärä, jotka täyttävät seuraavat ehdot:

  Kaupunki $s$ ja kaupunki $t$ sijaitsevat lyhimmällä polulla kaupungin $1$ ja kaupungin $A_j$ välillä, ja kuljettaessa kaupungista $1$ kaupunkiin $A_j$ kaupunkiin $s$ saavutaan ennen kaupunkia $t$, ja kaupungin $s$ eloisuuden arvo on aidosti suurempi kuin kaupungin $t$ eloisuuden arvo.

  Tässä kaupungin $1$ ja kaupungin $A_j$ välisellä polulla sijaitseviin kaupunkeihin luetaan mukaan myös kaupunki $1$ ja kaupunki $A_j$. Huomaa, että lyhin polku kaupungin $1$ ja kaupungin $A_j$ välillä on yksikäsitteinen.

• Kaikkien kaupungin $1$ ja kaupungin $A_j$ välisellä polulla sijaitsevien kaupunkien eloisuuden arvot muuttuvat kaupungin $B_j$ eloisuuden arvoksi.

Haluat tietää kunkin rakennustyön kustannuksen.

Tehtävä

Kun annetaan tiedot kaupungeista ja tienrakennustöistä, kirjoita ohjelma, joka laskee kunkin rakennustyön kustannuksen.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää kokonaisluvun $N$. Tämä tarkoittaa, että JOI-kuningaskunnassa on $N$ kaupunkia.
• Syötteen toinen rivi sisältää $N$ välilyönnein erotettua kokonaislukua $C_1, C_2, \cdots C_N$. Tämä tarkoittaa, että kaupungin $i$ ($1 \le i \le N$) eloisuuden alkuarvo on $C_i$.
• Seuraavien $N-1$ rivin $j$-s rivi ($1 \le j \le N-1$) sisältää kaksi välilyönnillä erotettua kokonaislukua $A_j$, $B_j$. Tämä tarkoittaa, että kaupunki $A_j$ ja kaupunki $B_j$ on valittu $j$-ttä tienrakennustyötä varten.

Tuloste

Kirjoita $N-1$ riviä vakiotulosteeseen. Tulosteen $j$-s rivi ($1 \le j \le N-1$) sisältää $j$-nnen tienrakennustyön kustannuksen.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

• $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$).
• Käyttämällä ennen $j$-ttä rakennustyötä rakennettuja teitä kaupungista $1$ pääsee kaupunkiin $A_j$ eikä kaupungista $1$ pääse kaupunkiin $B_j$ ($1 \le j \le N-1$).

Osatehtävät

Tehtävässä on 3 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [7 pistettä]

• $N \le 500$.

Osatehtävä 2 [9 pistettä]

• $N \le 4000$.

Osatehtävä 3 [84 pistettä]

Ei ole muita rajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

0
0
0
2

Huomautus

Esimerkkisyötteessä 1 rakennustyöt suoritetaan seuraavasti:

• Ensimmäisessä rakennustyössä ei ole yhtään ehtoja täyttävää paria $(s,t)$, joten kustannus on $0$. Rakennetaan kaupungin $1$ ja kaupungin $2$ yhdistävä tie, ja kaupungin $1$ eloisuuden arvoksi muuttuu $2$.
• Toisessa rakennustyössä ei myöskään ole yhtään ehtoja täyttävää paria $(s,t)$, joten kustannus on $0$. Rakennetaan kaupungin $2$ ja kaupungin $3$ yhdistävä tie, ja kaupungin $1$ sekä kaupungin $2$ eloisuuden arvoiksi muuttuu $3$.
• Kolmannessa rakennustyössä ei myöskään ole yhtään ehtoja täyttävää paria $(s,t)$, joten kustannus on $0$. Rakennetaan kaupungin $2$ ja kaupungin $4$ yhdistävä tie, ja kaupungin $1$ sekä kaupungin $2$ eloisuuden arvoiksi muuttuu $4$.
• Neljännessä rakennustyössä kaksi paria $(s,t)=(1,3),(2,3)$ täyttää ehdot, joten kustannus on $2$. Rakennetaan kaupungin $3$ ja kaupungin $5$ yhdistävä tie, ja kaupungin $1$, kaupungin $2$ sekä kaupungin $3$ eloisuuden arvoiksi muuttuu $5$.

Syöte 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

Tuloste 2

0
0
0
1
1
0
1
2
3