На ферме Farmer John $N$ амбаров ($2\le N\le2\cdot10^5$), номера $1\ldots N$, и $N-1$ дорог между парами. По дорогам можно попасть из любого амбара в любой. В амбаре $j$ сейчас $h_j$ тюков сена ($1\le h_j\le10^9$).

Чтобы порадовать коров, FJ переносит сено до равных количеств. Выбирает два соединённых дорогой амбара и приказывает работникам перенести из первого во второй любое положительное целое число тюков, не больше текущего количества в первом.

Найдите последовательность с минимальным числом приказов. Она существует.

Входные данные

Первая строка — $N$.

Вторая — $h_j$ через пробел, $j=1\ldots N$.

Последние $N-1$ строк — номера $u_i,v_i$ через пробел, двусторонняя дорога между ними.

Выходные данные

Выведите минимум приказов, затем столько же приказов, по одному в строке.

Приказ — три положительных целых через пробел: источник, получатель, число переносимых тюков.

При нескольких решениях любое.

Примеры

Входные данные 1

4
2 1 4 5
1 2
2 3
2 4

Выходные данные 1

3
3 2 1
4 2 2
2 1 1

Примечание

В примере $12$ тюков, $4$ амбара, в конце каждому $3$. Приказы означают:

1. Из $3$ в $2$ перенести $1$ тюк.

2. Из $4$ в $2$ перенести $2$ тюка.

3. Из $2$ в $1$ перенести $1$ тюк.

Подзадачи

• Тесты $2\ldots8$: $N\le5000$.

• Тесты $7\ldots10$: $v_i=u_i+1$.

• Тесты $11\ldots16$: без дополнительных ограничений.

Автор задачи: Aryansh Shrivastava