Izvanzemaljci

Είναι γνωστό ότι μια ομάδα Ρώσων επιστημόνων ανακάλυψε έναν εξωγήινο πολιτισμό το ~2016~. Ο δορυφόρος τους κατάφερε να συλλάβει ~K~ τετράγωνες εικόνες υψηλής ανάλυσης που άλλαξαν για πάντα την πορεία της ανθρώπινης ιστορίας. Σήμερα, μισή δεκαετία αργότερα, σχεδόν κάθε μέρος του κόσμου έχει το δικό του διαστημικό πρόγραμμα που ερευνά εξωγήινους.
Αλίμονο, στην Κροατία αποφασίσαμε να αντιμετωπίσουμε μερικά πιο σημαντικά προβλήματα, το οποίo αφήνει την επιστημονική έρευνα στους ώμους λίγων ενθουσιωδών. Ο Vladimir είναι ένας από αυτούς.
Δυστυχώς, ο Vladimir δεν έχει αρκετούς πόρους για ένα διαστημόπλοιο ή ένα ακριβό τηλεσκόπιο, αλλά μπορεί να αντέξει οικονομικά ένα αερόστατο και ένα κινητό τηλέφωνο. Αντί για εξωγήινο πολιτισμό, αποφάσισε να ψάξει για σημάδια ευφυούς ζωής στον πλανήτη του. Κοιτάζοντας κάτω από το αερόστατο, ο Vladimir παρατηρεί ακριβώς ~N~ άτομα. Αποφάσισε να τραβήξει ακριβώς ~K~ τετράγωνες εικόνες μέσης ανάλυσης έτσι ώστε κάθε άτομο να φαίνεται ακριβώς σε μία εικόνα. Επίσης, δεν θέλει καμία λεπτομέρεια να είναι ορατή σε περισσότερες από μία εικόνες. Επιπλέον, θεωρεί σημαντικό ότι η μεγαλύτερη περιοχή που είναι ορατή σε κάποια εικόνα είναι όσο το δυνατόν μικρότερη.
Ο Vladimir δεν είναι σπουδαίος προγραμματιστής, επομένως σας έστειλε μια επίσημη επεξήγηση και περιμένει τη βοήθειά σας.

Επίσημη Επεξήγηση

Υπάρχουν ~N~ ακέραια σημεία στο σύστημα συντεταγμένων. Πρέπει να βρείτε ακριβώς ~K~ διαζευγμένα τετράγωνα που καλύπτουν όλα τα ~N~ σημεία. Τα τετράγωνα πρέπει να έχουν πλευρές παράλληλες με τους άξονες συντεταγμένων και οι κορυφές τους πρέπει βρίσκονται σε ακέραιες συντεταγμένες. Το εμβαδόν του μεγαλύτερου τετραγώνου πρέπει να είναι όσο το δυνατόν μικρότερο.
Λέμε ότι ένα τετράγωνο καλύπτει ένα σημείο αν το σημείο είναι πλήρως μέσα του ή βρίσκεται στις κορυφές ή στις πλευρές του. Δύο τετράγωνα είναι χωριστά αν οι πλευρές τους δεν τέμνονται ή δεν εφάπτονται και κανένα από τα τετράγωνα δεν περιέχεται πλήρως στο άλλo.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N~ και ~K~ από την περιγραφή του προβλήματος.
Η ~i~-οστή από τις επόμενες ~N~ γραμμές περιέχει ακέραιους αριθμούς ~x_i~ και ~y_i (0 \le |x_i|,\,|y_i| \le 10^9 )~ που αντιπροσωπεύουν τις συντεταγμένες του ~i~-οστού σημείου (ανθρώπου). Όλα τα ~N~ σημεία θα είναι διαφορετικά.

Έξοδος

H ~i~-οστή από τις ~K~ γραμμές πρέπει να περιέχει τρεις ακέραιους αριθμούς ~x_i,\,y_i~ ~(0 \le |x_i|,\,|y_i| \le 3 \cdot 10^9)~ και ~l_i~ ~(1 \le l_i \le 2 \cdot 10^9)~,που ορίζουν μοναδικά τη θέση του ~i~-οστού τετραγώνου, έτσι ώστε το σημείο ~(x_i,\,y_i)~ να υποδηλώνει την κάτω αριστερή του κορυφή, και το ~l_i~ να υποδηλώνει το μήκος της πλευράς του. Εάν υπάρχουν πολλές σωστές λύσεις, εκτυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	5	~1 \le N \le 100\,000,\,K = 1~
2	21	~1 \le N \le 100\,000,\,K = 2~
3	12	~1 \le N \le 12,\,K = 3~
4	30	~1 \le N \le 1\,000,\,K = 3~
5	32	~1 \le N \le 100\,000,\,K = 3~

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

input

3 1
1 1
1 3
2 2

output

0 1 2

input

5 2
1 3
3 1
5 5
5 10
7 7

output

1 1 4
5 7 3

input

5 3
1 3
3 1
5 5
5 10
7 7

output

1 1 2
5 5 2
5 10 1

Επεξήγηση του 2ου και 3ου παραδείγματος