Șanț

Cei $n$ deţinuţi ai unei închisori, numerotaţi de la $1$ la $n$, trebuie să sape un şanţ dispus în linie dreaptă între două puncte $A$ şi $B$, situate la distanţa de $250$ km unul de celălalt, pe care există $251$ borne kilometrice numerotate de la $0$ la $250$. Fiecare deţinut are însă o pretenţie, "e doar democraţie, nu?": el doreşte să sape doar undeva în zona dintre borna $x$ şi borna $y$. Pe lângă aceste pretenţii închisoarea se confruntă şi cu o altă problemă: nu are suficienţi paznici angajaţi.

Cerinţă

Cunoscându-se numărul $n$ de deţinuţi şi pretenţiile lor, să se determine locul/locurile unde vor fi puşi deţinuţii să sape într-o zi de muncă, respectându-se pretenţiile lor, astfel încât numărul de paznici necesari pentru a păzi cei $n$ deţinuţi să fie minim. Intervalul în care poate păzi un paznic nu poate conţine două sau mai multe zone disjuncte dintre cele exprimate de deţinuţi în preferinţele lor.

Date de intrare

Fişierul de intrare sant.in are pe prima linie numărul $n$ de deţinuţi. Pe fiecare dintre următoarele $n$ linii există câte două numere naturale, $a_i \ b_i$, separate printr-un spaţiu $(a_i \leq b_i)$, care reprezintă pretenţia deţinutului. Mai exact pe linia $i+1 \ (1 \leq i \leq n)$ este descrisă pretenţia deţinutului cu numărul de ordine $i$.

Date de ieșire

Fişierul de ieşire sant.out va conţine pe prima linie numărul natural $k$ reprezentând numărul minim de paznici necesari pentru paza celor $n$ deţinuţi scoşi la lucru. Pe următoarele $2 \cdot k$ linii vor fi descrise locurile unde vor fi puşi să sape deţinuţii, astfel: fiecare pereche de linii $(2 \cdot j, 2 \cdot j+1)$ va conţine pe linia $2 \cdot j$ trei numere naturale $p \ x_j \ y_j$, separate prin câte un spaţiu reprezentând numărul de ordine al paznicului şi bornele kilometrice $x_j$ şi $y_j$ unde va păzi paznicul $p$, iar pe linia $2 \cdot j+1$ vor fi scrise numerele de ordine ale deţinuţilor care sapă în această zonă, separate prin câte un spaţiu, ordonate crescător.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$;
• $0 \leq a_i \leq b_i \leq 250$, pentru orice $i$, $1 \leq i \leq n$;
• $0 \leq x_j \leq y_j \leq 250$, pentru orice $j$, $1 \leq j \leq k$;
• Un deţinut poate să sape şi într-un singur punct ("în dreptul bornei kilometrice numerotată cu $x$");
• În cazul în care există mai multe soluţii se va afişa una singură;
• Numerele de ordine ale paznicilor vor fi scrise în fişier în ordine crescătoare;
• Numerotarea paznicilor începe de la $1$.
• Soluția nu este unică!

Exemplul 1

sant.in

3
0 20
8 13
30 60	

sant.out

2
1 8 13
1 2
2 30 60
3

Explicație

Sunt necesari $2$ paznici: paznicul $1$ va păzi între borna $8$ şi borna $13$, iar deţinuţii păziţi sunt $1$ şi $2$; paznicul $2$ va păzi între borna $30$ şi borna $60$, iar deţinutul păzit este $3$.

Exemplul 2

sant.in

4
10 20
2 5
30 40
5 7

sant.out

3
1 10 20
1
2 5 5
2 4
3 30 40
3

Explicație

Sunt necesari $3$ paznici: paznicul $1$ va păzi între borna $10$ şi borna $20$, iar deţinutul păzit este $1$; paznicul $2$ va păzi la borna $5$, iar deţinuţii păziţi sunt $2$ şi $4$; paznicul $3$ va păzi între borna $30$ şi borna $40$, iar deţinutul păzit este $3$.

Exemplul 3

sant.in

5
10 30
30 32
0 30
27 30
27 28

sant.out

2
1 30 30
1 2 3 4
2 27 28
5

Explicație

Sunt necesari $2$ paznici: paznicul $1$ va păzi la borna $30$, iar deţinuţii păziţi sunt $1$, $2$, $3$ şi $4$; paznicul $2$ va păzi între borna $27$ şi borna $28$, iar deţinutul păzit este $5$.