Ramazan postanowił zająć się poważnym biznesem — uprawą kapusty.

Pole do uprawy kapusty jest nieskończoną siatką komórek. W każdej komórce pola można posadzić jedną główkę kapusty.

Ramazan obsadził tylko część pola. Zaplanował wykorzystanie kilku prostokątnych obszarów, przy czym niektóre z nich mogą się nakładać. Komórka pola należy do uprawy, jeśli leży w co najmniej jednym z prostokątów.

Formalnie Ramazan wybrał $n$ prostokątnych obszarów $(x_i^L,y_i^L,x_i^R,y_i^R)$ ($x_i^L\le x_i^R$, $y_i^L\le y_i^R$, $1\le i\le n$). Komórka $(x,y)$ zawiera kapustę, jeśli istnieje co najmniej jeden wybrany prostokąt $i$ ($1\le i\le n$), taki że $x_i^L\le x\le x_i^R$ i $y_i^L\le y\le y_i^R$.

W przeszłości Ramazan był programistą (i zwycięzcą), dlatego postanowił używać robotów ze sztuczną inteligencją do okresowej pielęgnacji upraw. Jeden robot może obsługiwać dowolny poziomy odcinek komórek $(x_1^{robot},x_2^{robot},y^{robot})$, czyli wszystkie komórki $(x,y)$, dla których $x_1^{robot}\le x\le x_2^{robot}$ i $y=y^{robot}$.

Ważne jest, aby roboty jeździły tylko po obszarach z uprawą. Ramazan zrozumiał, że aby zminimalizować liczbę robotów, należy używać poziomych odcinków, których nie można rozszerzyć. Ramazan użyje robota na odcinku komórek $(x_1^{robot},x_2^{robot},y^{robot})$, jeśli:

• Wszystkie komórki $(x,y)$, dla których $x_1^{robot}\le x\le x_2^{robot}$ i $y=y^{robot}$, należą do uprawy.
• Komórka $(x_1^{robot}-1,y^{robot})$ nie należy do uprawy.
• Komórka $(x_2^{robot}+1,y^{robot})$ nie należy do uprawy.

Twoim zadaniem jest zebranie ważnych statystyk dotyczących robotów, które będą pracować na plantacji. Powiemy, że para $(x_1,x_2)$ jest obsługiwana w wierszu $y$, jeśli istnieje robot pracujący dokładnie na odcinku $(x_1,x_2,y)$.

• Znajdź wszystkie pary $(x_1,x_2)$, które są obsługiwane w jakimkolwiek wierszu.
• Dla każdej takiej pary $(x_1,x_2)$ znajdź liczbę wierszy, w których jest obsługiwana.
• Dla każdej takiej pary $(x_1,x_2)$ znajdź maksymalną liczbę kolejnych wierszy, w których jest obsługiwana. Innymi słowy, znajdź największą liczbę $k$, dla której istnieje odcinek $k$ kolejnych wierszy $[y_1,y_2]$ ($y_2-y_1+1=k$), taki że w każdym wierszu $y_1\le y\le y_2$ para $(x_1,x_2)$ jest obsługiwana.

Wejście

Każdy test składa się z kilku przypadków testowych. Pierwszy wiersz zawiera jeden całkowity parametr $t$ ($1\le t\le200\,000$) — liczbę przypadków testowych. Następnie podane są ich opisy.

Pierwszy wiersz każdego przypadku testowego zawiera jedną liczbę całkowitą $n$ ($1\le n\le200\,000$) — liczbę wybranych prostokątnych obszarów.

Każdy z kolejnych $n$ wierszy zawiera cztery liczby całkowite $x_i^L,y_i^L,x_i^R,y_i^R$ ($1\le x_i^L\le x_i^R\le10^9$, $1\le y_i^L\le y_i^R\le10^9$) — opis wybranego prostokątnego obszaru.

Niech $N$ oznacza sumę $n$ po wszystkich przypadkach testowych w jednym teście. Gwarantuje się, że $N\le200\,000$.

Wyjście

Dla każdego przypadku testowego najpierw wypisz jedną liczbę całkowitą $p$ ($p\ge1$) — liczbę par $(x_1,x_2)$, które są obsługiwane w jakimkolwiek wierszu.

W każdym z kolejnych $p$ wierszy wypisz cztery liczby całkowite $x_1,x_2,cnt,k$ ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^9$). Liczba $cnt$ powinna być równa liczbie wierszy, w których para $(x_1,x_2)$ jest obsługiwana. Liczba $k$ powinna być równa maksymalnej liczbie kolejnych wierszy, w których para $(x_1,x_2)$ jest obsługiwana.

Wszystkie pary $(x_1,x_2)$ muszą być różne. Każdą parę, która jest obsługiwana w jakimkolwiek wierszu, należy wypisać dokładnie raz. Pary można wypisać w dowolnej kolejności.

Podzadania

Dla przypadku testowego niech $w$ oznacza szerokość pola, czyli $w=\max_{i=1}^n x_i^R$, a $h$ — wysokość pola, czyli $h=\max_{i=1}^n y_i^R$.

• Jeśli dla danego testu rozwiązanie niepoprawnie wyznacza zbiór par $(x_1,x_2)$ obsługiwanych w jakimkolwiek wierszu, otrzymuje werdykt „Błędna odpowiedź”.

• Jeśli we wszystkich testach danego podzadania i wymaganych podzadań rozwiązanie:

  • poprawnie wyznacza zbiór, ale nie wszystkie wartości $cnt$ są poprawne, otrzymuje $50\%$ punktów za podzadanie;
  • poprawnie wyznacza zbiór i wszystkie wartości $cnt$, ale nie wszystkie wartości $k$ są poprawne, otrzymuje $75\%$ punktów za podzadanie;
  • poprawnie wyznacza zbiór, wszystkie wartości $cnt$ i wszystkie wartości $k$, otrzymuje $100\%$ punktów za podzadanie.

Zwróć uwagę, że aby otrzymać częściowe punkty za podzadanie, nadal trzeba wypisać jakieś wartości $cnt$ i $k$ dla każdej pary $(x_1,x_2)$, ale nie muszą być one poprawne.

Przykład

Wejście 1

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

Wyjście 1

3
2 3 1 1
2 4 1 1
3 4 1 1
2
1 3 1 1
2 2 2 1
4
2 4 2 2
2 9 4 2
3 9 2 2
7 9 3 3
6
1 4 2 2
1 6 1 1
1 7 3 2
2 2 4 2
4 7 2 1
5 6 2 1

Uwagi

Pierwszy i drugi przypadek testowy z przykładu w treści zadania

W pierwszym przypadku testowym roboty będą używane na odcinkach $(2,3,2)$, $(2,4,3)$, $(3,4,4)$. Zatem pary $(2,3)$, $(2,4)$, $(3,4)$ są obsługiwane w jakimkolwiek wierszu, przy czym każda z nich jest obsługiwana dokładnie w jednym wierszu.

W drugim przypadku testowym roboty będą używane na odcinkach $(2,2,1)$, $(2,4,2)$, $(2,2,3)$. Zatem pary $(2,2)$ i $(2,4)$ są obsługiwane w jakimkolwiek wierszu. Para $(2,2)$ jest obsługiwana w wierszach $1,3$, a para $(2,4)$ — w wierszu $2$.

Trzeci i czwarty przypadek testowy z przykładu w treści zadania