monezi

Într-un depozit al monetăriei statului sosesc $n$ saci cu monezi. Șeful depozitului cunoaște numărul de monezi din fiecare sac și ar vrea să modifice conținutul sacilor, prin mutări de monezi dintr-un sac în altul, astfel încât în final, în fiecare sac să fie același număr de monezi. Ajutați șeful depozitului să obțină același număr de monezi în fiecare sac, prin efectuarea unui număr minim de mutări.

Date de intrare

În fișierul de intrare monezi.in este scris pe prima linie un număr întreg $n$, reprezentând numărul de saci. Pe fiecare din următoarele $n$ linii este scris un număr întreg, reprezentând numerele de monezi din fiecare sac.

Date de ieșire

Rezultatele se vor scrie în fișierul de ieșire monezi.out sub următoarea formă:

• Pe prima linie se scrie un număr întreg $m$, reprezentând numărul minim de mutări necesare.
• Pe următoarele $m$ linii se vor scrie câte 3 numere întregi $a$, $b$, $c$, separate prin spațiu, unde:
  • $a$ reprezintă numărul de ordine al sacului din care se mută monezi;
  • $b$ reprezintă numărul de ordine al sacului în care se mută monezi;
  • $c$ reprezintă numărul de monezi care se mută din sacul $a$ în sacul $b$.

Restricții și precizări

• $2 \leq n \leq 2\ 000$
• Numărul total de monezi din toți sacii este $\leq 1\ 000\ 000\ 000$.
• În cazul în care problema nu are soluție, se va scrie în fișier cuvântul NU, iar în cazul în care problema are mai multe soluții, se va afișa oricare din ele.

Exemplu

monezi.in

3
35
48
37

monezi.out

2
2 1 5
2 3 3