لمزرعة 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