Marius Nicoli (mariusn) N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact un interval din descompunere). De exemplu, pentru perechea 5,10, o descompunere în intervale este [5,5], [6,8],[9,10].
Dorim să realizăm o descompunere în intervale a tuturor celor M perechi de numere date, astfel încât să se îndeplinească condițiile următoare (notăm L = 1 + [log2N]).
- fiecare pereche să aibă în descompunere maxim
2*Lintervale. - numărul total de intervale distincte cu mai mult de un element care apar în descompuneri să nu depășească valoarea
N.
Cerința
Afișați descompunerea fiecărei perechi din fișierul de intrare.
Date de intrare
Pe prima linie a fisierului di.in se află două numere N și M, separate prin spațiu, cu semnificația de mai sus. Pe fiecare din următoarele M linii se găsesc câte 2 numere naturale separate prin câte un spațiu, X Y ce reprezintă câte o pereche ce trebuie descompusă.
Date de ieșire
Fișierul di.out conține M linii, pe fiecare aflându-se descompunerea unei perechi date în fișierul de intrare, în ordine. Primul element al unei linii reprezintă numărul de intervale ale unei descompuneri, notat K. Urmează apoi K+1 elemente în ordine strict crescătoare, E1, E2, ... Ek+1. Primul interval este [E1, E2], al doilea este [E2+1, E3] ... Ultimul interval este [Ek+1 ,E k+1 ].
Restricții și precizări
1 ≤ N ≤ 1000001 ≤ M ≤ 2000001 ≤ X ≤ Y ≤ NX ≤ Y
Exemplu:
di.in
7 10 1 4 1 5 1 6 1 7 2 5 2 6 2 7 3 6 3 7 4 7
di.out
1 1 4 2 1 4 5 2 1 4 6 1 1 7 3 2 2 4 5 3 2 2 4 6 3 2 2 4 7 2 3 4 6 3 3 4 6 7 2 4 4 7
Explicație
Pentru perechea 2,7 codificarea descompunerii este 2 2 4 7 reprezentând intervalele [2,2], [3,4], [5,7].