Slicice

Αφού έσκασε η πισίνα τους, ο Mirko και ο Slavko άρχισαν να συλλέγουν κάρτες. Στη γειτονιά τους, η συλλογή καρτών λαμβάνεται σοβαρά υπόψη και υπάρχουν αυστηροί κανόνες για την αγορά και εμπορία καρτών.
Η αγορά καρτών γίνεται πάντα από δύο παιδιά μαζί. Κάθε ένα από αυτά δίνει τα μισά από τα απαιτούμενα κεφάλαια και αγοράζονται δύο κάρτες. Στη συνέχεια κάνουν αγώνα δρόμου μέχρι το σιντριβάνι στο κέντρο της πόλης, όπου ο νικητής παίρνει και τις δύο κάρτες. Αν φτάσουν την ίδια ακριβώς ώρα, καθένας από αυτούς παίρνει από μια κάρτα.
Στην αρχή οι κανόνες λειτουργούσαν εντάξει, αλλά σύντομα άρχισαν οι κατηγορίες πως κάποια παιδιά δεν μπορούσαν να έχουν αποκτήσει τις κάρτες τους μόνο μέσω τέτοιων αγορών.
Μια μέρα όλα τα παιδιά συναντήθηκαν για να καταλάβουν αν υπήρχαν παρατυπίες. Κατάφεραν να συμφωνήσουν στον ακριβή αριθμό των καρτών που έχει ο καθένας. Έκαναν επίσης μια μερική λίστα με το ποιοι πήγαν στο κατάστημα με ποιον, αλλά δεν ξέρουν ποιος κέρδισε κάποιον από τους αγώνες και πήρε τα χαρτιά σε αυτές τις περιστάσεις.
Γράψτε ένα πρόγραμμα που καθορίζει ποιος συμμετείχε σε όλες τις αγορές που έγιναν και ποιος κέρδισε τους ακόλουθους αγώνες, ώστε μετά από όλες τις αγορές, οι μετρήσεις των καρτών να αντιστοιχούν στις δεδομένες μετρήσεις. Υποθέστε ότι πριν από οποιαδήποτε αγορά, τα παιδιά δεν είχαν κάρτες.
Εάν υπάρχουν πολλές πιθανές λύσεις, τυπώστε οποιαδήποτε από αυτές.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~M (1 \le N \le 100,\; 0 \le M \le 1\,000 )~, τον αριθμό των παιδιών και τον αριθμό των αγορών που θυμούνται. Τα παιδιά χαρακτηρίζονται από 1 έως ~N~. Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς, τον αριθμό των καρτών που έχει κάθε παιδί αυτήν τη στιγμή. Οι ακόλουθες γραμμές ~M~ περιέχουν δύο ακέραιους αριθμούς η καθεμία, τις ετικέτες των παιδιών που έκαναν την αγορά.

Έξοδος

Στην πρώτη γραμμή, τυπώστε τον συνολικό αριθμό αγορών.
Κάθε μία από τις ακόλουθες γραμμές πρέπει να περιγράφει μία αγορά. Η περιγραφή μιας αγοράς αποτελείται από τρεις αριθμούς: τις ετικέτες των παιδιών που έκαναν την αγορά και τον αριθμό ~0,\;1~ ή ~2~, πόσες κάρτες το πρώτο παιδί πήρε μετά τον αγώνα.
Σημείωση: Μια λύση θα υπάρχει πάντα, αν και όχι απαραίτητα μοναδική. Ο συνολικός αριθμός αγορών θα να είναι το πολύ ~1\,000~.

Παραδείγματα

input

2 3
5 1
1 2
1 2
1 2

output

3
1 2 1
1 2 2
1 2 2

Επεξήγηση του 1ου παραδείγματος:

Υπάρχουν μόνο δύο παιδιά, με τις ετικέτες ~1~ και ~2~. Το πρώτο παιδί θα πρέπει να καταλήξει με πέντε κάρτες, το δεύτερο με μια.
Μετά την πρώτη αγορά, κάθε ένα από τα παιδιά πήρε από μία κάρτα.
Μετά τη δεύτερη και την τρίτη αγορά, το πρώτο παιδί πήρε και τις δύο κάρτες και τις δύο φορές.

input

4 3
5 3 1 1
1 3
2 3
4 1

output

5
1 3 1
2 3 2
4 1 0
2 4 1
1 3 2

input

5 0
3 0 2 4 1

output

5
1 2 2
1 3 1
4 2 2
3 4 0
3 5 1