La fattoria di Farmer John ha $N$ fienili ($2\le N\le2\cdot10^5$), numerati $1\ldots N$, e $N-1$ strade che collegano coppie. Ogni fienile è raggiungibile da ogni altro. Il $j$ ha $h_j$ balle ($1\le h_j\le10^9$).

Per accontentare le mucche, FJ sposta fieno fino a quantità uguali. Sceglie due fienili collegati e ordina agli operai di spostare dal primo al secondo qualsiasi intero positivo di balle, non maggiore della quantità attuale nel primo.

Trova una sequenza con numero minimo di ordini. Esiste sicuramente.

Input

Prima riga: $N$.

Seconda: $h_j$ con spazi, $j=1\ldots N$.

Ultime $N-1$ righe: numeri $u_i,v_i$ con uno spazio, strada bidirezionale fra essi.

Output

Stampa il minimo di ordini e sequenza di quella lunghezza, uno per riga.

Ordine: tre interi positivi con spazi, origine, destinazione e balle da spostare.

Se vi sono più soluzioni, stampane una qualsiasi.

Esempi

Input 1

4
2 1 4 5
1 2
2 3
2 4

Output 1

3
3 2 1
4 2 2
2 1 1

Spiegazione

$12$ balle e $4$ fienili, alla fine $3$ ciascuno. Gli ordini significano:

1. Da $3$ a $2$, spostare $1$ balla.

2. Da $4$ a $2$, spostare $2$ balle.

3. Da $2$ a $1$, spostare $1$ balla.

Sottoproblemi

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

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

• Test $11\ldots16$: nessun vincolo aggiuntivo.

Autore del problema: Aryansh Shrivastava