Szachownica

Jest szachownica n na n. Chcemy na niej postawić n wież tak, żeby żadne dwie się nie biły. Ponadto każda wieża ma wyznaczony prostokąt, w którym ma się znajdować.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1<=N<=500000) - rozmiar szachownicy. W kolejnych N liniach znajdują się po cztery liczby całkowite xpi, ypi, xki, yki pomiędzy 1 i N włącznie. Oznaczają one, że współrzędne wieży numer i muszą spełniać warunki: xpi<=xi<=xki oraz ypi<=yi<=yki.

Wyjście

Na standardowe wyjście wypisz N wierszy, w każdym po dwie liczby od 1 do N. Będą to współrzędne x, y wieży numer i. Wybierz dowolne z możliwych ustawień. Załóż, że jakieś istnieje.

Przykład

Dla wejścia:
4
1 1 4 4
2 2 3 3
2 2 3 3
1 4 1 4
poprawnym wyjściem jest na przykład:
4 1
2 3
3 2
1 4