Farma Farmer John ma $N$ stodół ($2\le N\le2\cdot10^5$), numery $1\ldots N$, i $N-1$ dróg łączących pary. Z każdej można dotrzeć do każdej innej. Stodoła $j$ ma $h_j$ bel ($1\le h_j\le10^9$).

By zadowolić krowy, FJ przenosi siano do równych ilości. Wybiera dwie połączone drogą stodoły i każe pracownikom przenieść z pierwszej do drugiej dowolną dodatnią całkowitą liczbę bel, nie większą niż obecny zapas pierwszej.

Znajdź sekwencję z minimalną liczbą poleceń. Istnienie gwarantowane.

Wejście

Pierwszy wiersz: $N$.

Drugi: $h_j$ ze spacjami, $j=1\ldots N$.

Ostatnie $N-1$ wierszy: numery $u_i,v_i$ ze spacją, dwukierunkowa droga między nimi.

Wyjście

Wypisz minimum poleceń, potem sekwencję tej długości, jedno na wiersz.

Polecenie: trzy dodatnie całkowite ze spacjami, źródło, cel, przenoszone bele.

Jeśli wiele rozwiązań, wypisz dowolne.

Przykład

Wejście 1

4
2 1 4 5
1 2
2 3
2 4

Wyjście 1

3
3 2 1
4 2 2
2 1 1

Uwagi

$12$ bel i $4$ stodoły, na końcu po $3$. Polecenia oznaczają:

1. Z $3$ do $2$ przenieś $1$ belę.

2. Z $4$ do $2$ przenieś $2$ bele.

3. Z $2$ do $1$ przenieś $1$ belę.

Podzadania

• Testy $2\ldots8$: $N\le5000$.

• Testy $7\ldots10$: $v_i=u_i+1$.

• Testy $11\ldots16$: bez dodatkowych ograniczeń.

Autor zadania: Aryansh Shrivastava