A fazenda de Farmer John tem $N$ celeiros ($2\le N\le2\cdot10^5$), numerados $1\ldots N$, e $N-1$ estradas ligando pares. Pode-se ir de qualquer um a qualquer outro. O $j$ tem $h_j$ fardos ($1\le h_j\le10^9$).

Para agradar as vacas, FJ move feno para igualar quantidades. Escolhe dois celeiros ligados e manda os trabalhadores moverem do primeiro ao segundo qualquer inteiro positivo de fardos, no máximo a quantidade atual do primeiro.

Ache uma sequência com número mínimo de ordens. Sua existência é garantida.

Entrada

Primeira linha: $N$.

Segunda: $h_j$ com espaços, $j=1\ldots N$.

Últimas $N-1$ linhas: números $u_i,v_i$ com um espaço, estrada bidirecional entre eles.

Saída

Imprima o mínimo de ordens e sequência desse comprimento, uma por linha.

Ordem: três inteiros positivos com espaços, origem, destino e número de fardos movidos.

Havendo várias soluções, imprima qualquer uma.

Exemplos

Entrada 1

4
2 1 4 5
1 2
2 3
2 4

Saída 1

3
3 2 1
4 2 2
2 1 1

Explicação

$12$ fardos e $4$ celeiros, finalmente $3$ em cada. As ordens significam:

1. De $3$ a $2$, mover $1$ fardo.

2. De $4$ a $2$, mover $2$ fardos.

3. De $2$ a $1$, mover $1$ fardo.

Subtarefas

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

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

• Testes $11\ldots16$: sem restrições adicionais.

Autor do problema: Aryansh Shrivastava