Том і Джеррі несподівано стали керувати мережею банків!
Банки з’єднані дорогами, які утворюють дерево — тобто між будь-якими двома банками існує рівно один шлях. Серед усіх банків є два центральні: один належить Тому, а інший — Джеррі. Обидва центральні банки можуть друкувати гроші. Гарантовано, що центральні банки Тома та Джеррі безпосередньо з’єднані однією дорогою.
Після перевірки системи Том і Джеррі виявили, що всі банки повністю порожні. Тому вони склали план, скільки грошей має бути в кожному банку на початок року. Зокрема, в -му банку має опинитися рівно a_i доларів. Кожному банку потрібні кошти для роботи, тому всі значення a_i є додатними.
Необхідно виконати цей план таким чином:
Спочатку визначте, скільки доларів мають надрукувати центральні банки Тома та Джеррі й покласти на власні рахунки.
Після цього можна виконати не більше ніж переказів між банками за таким правилом: Обчислюється число — максимальна відстань між будь-якими двома непорожніми банками (банками з додатним балансом).
Вибираються будь-які два банки та , що знаходяться на відстані рівно , після чого довільна додатна ціла сума грошей переказується з банку до банку . Звісно, до переказу банк повинен мати щонайменше цю суму.
Визначте, скільки доларів мають надрукувати Том і Джеррі, та побудуйте послідовність переказів, яка забезпечить виконання плану. Якщо це неможливо, виведіть impossible.
У першому рядку задано ціле число — кількість банків.
У другому рядку задано два цілі числа — номери центральних банків (від до включно). Гарантовано, що вони різні та безпосередньо з’єднані дорогою.
У кожному з наступних (n - 1) рядків задано по два цілі числа та — банки, з’єднані дорогою.
В останньому рядку задано додатних цілих чисел a_1, a_2, \dots, a_n — кількість доларів, яку повинен отримати кожен банк.
2 \le n \le 4000,
1 \le a_i \le 10^9.
Якщо виконати план неможливо, виведіть impossible.
Інакше в першому рядку виведіть два цілі числа — кількість доларів, яку повинні надрукувати перший і другий центральні банки відповідно.
У другому рядку виведіть ціле число — кількість переказів (0 \le k \le n).
У кожному з наступних рядків виведіть по три цілі числа , та , які означають, що необхідно переказати доларів з банку до банку . Перекази слід виводити в порядку їх виконання.
Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
Example