Það eru $N$ borgir í JOI-konungsríkinu, sem eru númeraðar með tölunum frá $1$ til $N$. Borg $1$ er höfuðborgin. Hver borg hefur gildi sem kallast lífgleði og upphafsgildi lífgleði borgar $i$ ($1 \le i \le N$) er $C_i$.

Vegur í JOI-konungsríkinu tengir tvær ólíkar borgir í báðar áttir. Í upphafi er enginn vegur í JOI-konungsríkinu. Þú hefur skipulagt $N-1$ vegalagningar. $j$-ta framkvæmdin ($1 \le j \le N-1$) er skipulögð á eftirfarandi hátt.

• Tvær borgir, $A_j$ og $B_j$, eru valdar, þegar hægt er að komast frá borg $1$ til borgar $A_j$ en ekki er hægt að komast frá borg $1$ til borgar $B_j$ með því að nota eingöngu vegi sem hafa verið lagðir á þeim tímapunkti.

• Þú leggur veg sem tengir borg $A_j$ og borg $B_j$. Kostnaðurinn við þessa framkvæmd er fjöldi para borga $(s,t)$ sem uppfylla eftirfarandi skilyrði:

  Borg $s$ og borg $t$ liggja á stystu leiðinni milli borgar $1$ og borgar $A_j$, og þegar farið er frá borg $1$ til borgar $A_j$ er komið að borg $s$ á undan borg $t$, og gildi lífgleði borgar $s$ er strangt stærra en gildi borgar $t$.

  Hér teljast borg $1$ og borg $A_j$ meðal þeirra borga sem liggja á leiðinni milli borgar $1$ og borgar $A_j$. Athugið að stysta leiðin milli borgar $1$ og borgar $A_j$ er ótvíræð.

• Gildi lífgleði allra borga sem liggja á leiðinni milli borgar $1$ og borgar $A_j$ breytast í gildi lífgleði borgar $B_j$.

Þú vilt vita kostnaðinn við hverja framkvæmd.

Verkefni

Gefin eru gögn um borgir og vegalagningar. Skrifið forrit sem reiknar út kostnaðinn við hverja framkvæmd.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

• Fyrsta línan í inntakinu inniheldur heiltölu $N$. Þetta þýðir að það eru $N$ borgir í JOI-konungsríkinu.
• Önnur línan í inntakinu inniheldur $N$ heiltölur $C_1, C_2, \cdots C_N$ aðskildar með bilum. Þetta þýðir að upphafsgildi lífgleði borgar $i$ ($1 \le i \le N$) er $C_i$.
• $j$-ta línan ($1 \le j \le N-1$) af næstu $N-1$ línum inniheldur tvær heiltölur $A_j$, $B_j$ aðskildar með bili. Þetta þýðir að borg $A_j$ og borg $B_j$ eru valdar fyrir $j$-tu vegalagninguna.

Úttak

Skrifið $N-1$ línur í staðalúttak. $j$-ta línan ($1 \le j \le N-1$) í úttakinu skal innihalda kostnaðinn við $j$-tu vegalagninguna.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

• $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$).
• Með því að nota vegi sem lagðir voru fyrir $j$-tu framkvæmdina er hægt að komast frá borg $1$ til borgar $A_j$ og ekki er hægt að komast frá borg $1$ til borgar $B_j$ ($1 \le j \le N-1$).

Undirverkefni

Það eru 3 undirverkefni. Stigagjöf og viðbótarskorður hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [7 stig]

• $N \le 500$.

Undirverkefni 2 [9 stig]

• $N \le 4000$.

Undirverkefni 3 [84 stig]

Engar frekari skorður eru til staðar.

Dæmi

Inntak 1

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

Úttak 1

0
0
0
2

Skýring

Í sýnidæmi 1 eru framkvæmdirnar gerðar sem hér segir:

• Í fyrstu framkvæmdinni eru engin pör $(s,t)$ sem uppfylla skilyrðin, svo kostnaðurinn er $0$. Vegur sem tengir borg $1$ og borg $2$ er lagður og gildi lífgleði borgar $1$ breytist í $2$.
• Í annarri framkvæmdinni eru heldur engin pör $(s,t)$ sem uppfylla skilyrðin, svo kostnaðurinn er $0$. Vegur sem tengir borg $2$ og borg $3$ er lagður og gildi lífgleði borgar $1$ og borgar $2$ breytast í $3$.
• Í þriðju framkvæmdinni eru heldur engin pör $(s,t)$ sem uppfylla skilyrðin, svo kostnaðurinn er $0$. Vegur sem tengir borg $2$ og borg $4$ er lagður og gildi lífgleði borgar $1$ og borgar $2$ breytast í $4$.
• Í fjórðu framkvæmdinni uppfylla tvö pör $(s,t)=(1,3),(2,3)$ skilyrðin, svo kostnaðurinn er $2$. Vegur sem tengir borg $3$ og borg $5$ er lagður og gildi lífgleði borgar $1$, borgar $2$ og borgar $3$ breytast í $5$.

Inntak 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

Úttak 2

0
0
0
1
1
0
1
2
3