בחוות 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