На фермі Джона є \(N\) комор (\(2 \leq N \leq 2\cdot 10^5\)) пронумерованих \(1 \dots N\). Є \(N-1\) доріг, де кожна дорога з'єднує дві комори і від будь-якої комори до будь-якої іншої можна дістатися за допомогою деякої послідовності доріг. У \(j\)-ій коморі є \(h_j\) снопів сіна (\(1\le h_j\le 10^9\)).

ФД хоче перемістити сіно так, щоб у кожній коморі була однакова кількість снопів. Він може вибрати будь-яку пару комор з'єднаних дорогою і перевезти цілу кількість снопів сіна з першої комори у другу.

Визначте послідовність дій ФД, щоб досягти мети за мінімальну кількість дій. Гарантується, що така послідовність існує.

Формат вхідних даних

Перший рядок входу містить значення \(N.\)

Другий рядок містить розділені одиночними пробілами значення \(h_j\) для \(j = 1 \dots N\).

Кожен з останніх \(N-1\) рядків містить два розділені одиночними пробілами числа \(u_i \ v_i\), що вказують, що є двонаправлена дорога, що з'єднує комори \(u_i\) і \(v_i\).

Формат вихідних даних

Виведіть мінімальну кількість дій, за якими слідує послідовність цих дій по одній у рядку.

Кожна дія описується трьома розділеними одиночними пробілами додатними цілими числами: комора-джерело, комора-приймач, кількість снопів сіна, що перевозяться з джерела до приймача.

Якщо є безліч рішень, виводьте будь-яке.

Приклад вхідних даних

4
2 1 4 5
1 2
2 3
2 4

Приклад вихідних даних

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-8 \(N\leq 5000\)
• У тестах 7-10 \(v_i=u_i+1\)
• У тестах 11-16 немає додаткових обмежень