patrate

Enunţ

Pe o foaie de matematică sunt $5000 \times 5000$ de pătrăţele cu latura egală cu $1$ cm. Pătrăţelele sunt evident organizate în $5000$ de linii (numerotate de sus în jos de la $1$ la $5000$) şi $5000$ de coloane (numerotate de la stânga la dreapta de la $1$ la $5000$).
Poziţia fiecărui pătrăţel de pe foaie este caracterizată prin numărul liniei şi numărul coloanei pe care se află pătrăţelul. Pe foaie sunt înnegrite $n$ pătrăţele.
Trebuie să desenăm pe foaia de matematică o mulţime de pătrate care să îndeplinească următoarele condiţii:

• aria intersecţiei între oricare două pătrate din această mulţime este egală cu $0$;
• oricare dintre pătratele acestei mulţimi este alcătuit doar din pătrăţele întregi;
• oricare pătrăţel negru aparţine exact unuia dintre pătratele mulţimii;
• pentru oricare dintre pătratele acestei mulţimi, dacă notăm cu $S$ aria pătratului, atunci suprafaţa ocupată de pătrăţelele negre din interiorul respectivului pătrat aparţine intervalului $[S/k, 4S/k)$, unde $k$ este un număr natural nenul dat.

Cerință

Scrieţi un program care determine o mulţime de pătrate care să respecte condiţiile de mai sus.

Date de intrare

Fişierul de intrare patrate.in conţine pe prima linie două numere naturale nenule separate prin spaţiu $n$ şi $k$, cu semnificaţia din enunţ. Pe fiecare dintre următoarele $n$ linii se află câte două numere naturale nenule separate prin spaţiu, reprezentând poziţia unui pătrăţel negru.

Date de ieșire

În fişierul de ieşire patrate.out se va scrie pe prima linie un număr natural nenul $np$, reprezentând numărul de pătrate din mulţime. Pe fiecare dintre următoarele $np$ linii se vor afla trei numere naturale nenule separate prin câte un spaţiu; primele două valori vor reprezenta linia, respectiv coloana pe care se află pătrăţelul situat în colţul din stânga-sus al pătratului respectiv, iar a treia valoare va reprezenta lungimea laturii respectivului pătrat.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $5 \leq k \leq 10$;
• Coordonatele pătrăţelelor negre (linie, coloană) sunt numere naturale din intervalul $[1, 1000]$.

Exemplul

patrate.in

19 5
1 1
1 2
2 1
2 2
3 1
3 3
4 3
5 5
5 6
5 7
6 6
6 7
10 7
10 8
7 9
8 10
8 9
9 9
10 9

patrate.out

2
1 1 4
5 5 6

Explicație

Există mai multe soluţii posibile. O altă soluţie ar putea fi:
$4$
$1 \ 1 \ 4$
$5 \ 5 \ 4$
$7 \ 9 \ 4$
$10 \ 7 \ 2$