Рамазан beschloss, sich einem ernsthaften Geschäft zu widmen: dem Anbau von Kohl.

Das Kohlfeld ist ein unendliches Raster aus Zellen. In jeder Zelle kann ein Kohlkopf gepflanzt werden.

Рамазан bepflanzte nur einen Teil des Feldes. Er plante, mehrere rechteckige Flächen zu verwenden, wobei sich einige von ihnen überschneiden können. Eine Zelle gehört zur Bepflanzung, wenn sie in mindestens einem der Rechtecke liegt.

Formal wählte Рамазан $n$ rechteckige Flächen $(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$). Die Zelle $(x,y)$ enthält Kohl, wenn mindestens ein gewähltes Rechteck $i$ ($1\le i\le n$) existiert, für das $x_i^L\le x\le x_i^R$ und $y_i^L\le y\le y_i^R$ gelten.

Früher war Рамазан Programmierer (und Sieger), daher beschloss er, Roboter mit künstlicher Intelligenz zur regelmäßigen Pflege der Bepflanzung einzusetzen. Ein Roboter kann einen beliebigen horizontalen Abschnitt von Zellen $(x_1^{robot},x_2^{robot},y^{robot})$ betreuen, also alle Zellen $(x,y)$ mit $x_1^{robot}\le x\le x_2^{robot}$ und $y=y^{robot}$.

Es ist wichtig, dass die Roboter nur durch bepflanzte Bereiche fahren. Er erkannte, dass zur Minimierung der Anzahl der Roboter horizontale Abschnitte verwendet werden müssen, die nicht erweitert werden können. Рамазан setzt auf dem Abschnitt $(x_1^{robot},x_2^{robot},y^{robot})$ einen Roboter ein, wenn:

• Alle Zellen $(x,y)$ mit $x_1^{robot}\le x\le x_2^{robot}$ und $y=y^{robot}$ zur Bepflanzung gehören;
• Die Zelle $(x_1^{robot}-1,y^{robot})$ nicht zur Bepflanzung gehört;
• Die Zelle $(x_2^{robot}+1,y^{robot})$ nicht zur Bepflanzung gehört.

Ihre Aufgabe ist es, wichtige Statistiken über die Roboter zu sammeln, die auf der Plantage arbeiten werden. Ein Paar $(x_1,x_2)$ heißt in der Zeile $y$ betreut, wenn ein Roboter genau auf dem Abschnitt $(x_1,x_2,y)$ arbeitet.

• Finden Sie alle Paare $(x_1,x_2)$, die in irgendeiner Zeile betreut werden.
• Finden Sie für jedes solche Paar $(x_1,x_2)$ die Anzahl der Zeilen, in denen es betreut wird.
• Finden Sie für jedes solche Paar $(x_1,x_2)$ die maximale Anzahl aufeinanderfolgender Zeilen, in denen es betreut wird. Anders ausgedrückt: Finden Sie die größte Zahl $k$, für die ein Intervall aus $k$ aufeinanderfolgenden Zeilen $[y_1,y_2]$ ($y_2-y_1+1=k$) existiert, sodass das Paar $(x_1,x_2)$ in jeder Zeile $y_1\le y\le y_2$ betreut wird.

Eingabe

Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $t$ ($1\le t\le200\,000$), die Anzahl der Testfälle. Danach folgen die Beschreibungen der Testfälle.

Die erste Zeile jedes Testfalls enthält eine einzige ganze Zahl $n$ ($1\le n\le200\,000$), die Anzahl der gewählten rechteckigen Flächen.

Jede der folgenden $n$ Zeilen enthält vier ganze Zahlen $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$), die die gewählten rechteckigen Flächen beschreiben.

Mit $N$ bezeichnen wir die Summe von $n$ über alle Testfälle eines Tests. Es ist garantiert, dass $N\le200\,000$ gilt.

Ausgabe

Geben Sie für jeden Testfall zuerst eine ganze Zahl $p$ ($p\ge1$) aus, die Anzahl der Paare $(x_1,x_2)$, die in irgendeiner Zeile betreut werden.

Geben Sie in jeder der folgenden $p$ Zeilen vier ganze Zahlen $x_1,x_2,cnt,k$ aus ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^9$). Die Zahl $cnt$ muss der Anzahl der Zeilen entsprechen, in denen das Paar $(x_1,x_2)$ betreut wird. Die Zahl $k$ muss der maximalen Anzahl aufeinanderfolgender Zeilen entsprechen, in denen das Paar $(x_1,x_2)$ betreut wird.

Alle Paare $(x_1,x_2)$ müssen verschieden sein. Jedes Paar, das in irgendeiner Zeile betreut wird, muss genau einmal ausgegeben werden. Die Paare dürfen in beliebiger Reihenfolge ausgegeben werden.

Teilaufgaben

Für einen Testfall bezeichnen wir mit $w$ die Breite des Feldes, also $w=\max_{i=1}^n x_i^R$, und mit $h$ die Höhe des Feldes, also $h=\max_{i=1}^n y_i^R$.

• Wenn Ihre Lösung für einen Test die Menge der Paare $(x_1,x_2)$, die in irgendeiner Zeile betreut werden, falsch bestimmt, erhält sie das Urteil „Falsche Antwort“.

• Wenn die Lösung in allen Tests der Teilaufgabe und ihrer erforderlichen Teilaufgaben:

  • die Menge richtig bestimmt, aber nicht alle $cnt$ richtig sind, erhält sie $50\%$ der Punkte für die Teilaufgabe;
  • die Menge und alle $cnt$ richtig bestimmt, aber nicht alle $k$ richtig sind, erhält sie $75\%$ der Punkte für die Teilaufgabe;
  • die Menge, alle $cnt$ und alle $k$ richtig bestimmt, erhält sie $100\%$ der Punkte für die Teilaufgabe.

Beachten Sie, dass Sie auch für Teilpunkte für jedes Paar $(x_1,x_2)$ irgendwelche Werte für $cnt$ und $k$ ausgeben müssen; diese müssen aber nicht richtig sein.

Beispiele

Eingabe 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

Ausgabe 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

Hinweis

Der erste und zweite Testfall des Tests aus der Aufgabenstellung

Im ersten Testfall werden Roboter auf den Abschnitten $(2,3,2)$, $(2,4,3)$ und $(3,4,4)$ eingesetzt. Daher werden die Paare $(2,3)$, $(2,4)$ und $(3,4)$ in irgendeiner Zeile betreut, jedes davon in genau einer Zeile.

Im zweiten Testfall werden Roboter auf den Abschnitten $(2,2,1)$, $(2,4,2)$ und $(2,2,3)$ eingesetzt. Daher werden die Paare $(2,2)$ und $(2,4)$ in irgendeiner Zeile betreut. Das Paar $(2,2)$ wird in den Zeilen $1,3$ betreut, das Paar $(2,4)$ in Zeile $2$.

Der dritte und vierte Testfall des Tests aus der Aufgabenstellung