Ramazan ha deciso di dedicarsi a un'attività seria: coltivare cavoli.

Il campo per coltivare i cavoli è una griglia infinita di celle. In ogni cella si può piantare un cavolo.

Ramazan ha piantato soltanto una parte del campo. Aveva previsto di utilizzare diversi appezzamenti rettangolari, ma alcuni di essi possono intersecarsi. Una cella appartiene alla coltivazione se si trova in almeno uno dei rettangoli.

Formalmente, Ramazan ha scelto $n$ appezzamenti rettangolari $(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$). La cella $(x,y)$ contiene un cavolo se esiste almeno un rettangolo scelto $i$ ($1\le i\le n$) tale che $x_i^L\le x\le x_i^R$ e $y_i^L\le y\le y_i^R$.

In passato Ramazan era un programmatore (e un vincitore), perciò ha deciso di utilizzare robot dotati di intelligenza artificiale per la manutenzione periodica della coltivazione. Un robot può servire un qualsiasi segmento orizzontale di celle $(x_1^{robot},x_2^{robot},y^{robot})$, cioè tutte le celle $(x,y)$ tali che $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$.

È importante che i robot si spostino soltanto nelle aree coltivate. Ramazan ha capito che, per minimizzare il numero di robot, è importante utilizzare segmenti orizzontali che non si possono estendere. Ramazan utilizzerà un robot sul segmento di celle $(x_1^{robot},x_2^{robot},y^{robot})$ se:

• Tutte le celle $(x,y)$ tali che $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$ appartengono alla coltivazione.
• La cella $(x_1^{robot}-1,y^{robot})$ non appartiene alla coltivazione.
• La cella $(x_2^{robot}+1,y^{robot})$ non appartiene alla coltivazione.

Il vostro compito è raccogliere statistiche importanti sui robot che lavoreranno nella piantagione. Diremo che la coppia $(x_1,x_2)$ è servita nella riga $y$ se esiste un robot che lavora esattamente sul segmento $(x_1,x_2,y)$.

• Trovate tutte le coppie $(x_1,x_2)$ che sono servite in qualche riga.
• Per ogni coppia $(x_1,x_2)$ trovata, determinate il numero di righe in cui è servita.
• Per ogni coppia $(x_1,x_2)$ trovata, determinate il numero massimo di righe consecutive in cui è servita. In altre parole, trovate il massimo numero $k$ tale che esista un intervallo di $k$ righe consecutive $[y_1,y_2]$ ($y_2-y_1+1=k$) per cui, in ogni riga $y_1\le y\le y_2$, la coppia $(x_1,x_2)$ è servita nella riga $y$.

Input

Ogni test consiste di più casi di test. La prima riga contiene un intero $t$ ($1\le t\le 200\,000$): il numero di casi di test. Seguono le descrizioni dei casi di test.

La prima riga di ciascun caso di test contiene un solo intero $n$ ($1\le n\le 200\,000$): il numero di appezzamenti rettangolari scelti.

Ciascuna delle successive $n$ righe contiene quattro interi $x_i^L,y_i^L,x_i^R,y_i^R$ ($1\le x_i^L\le x_i^R\le 10^9$, $1\le y_i^L\le y_i^R\le 10^9$): la descrizione degli appezzamenti rettangolari scelti.

Indichiamo con $N$ la somma di $n$ su tutti i casi di test di un test. È garantito che $N\le 200\,000$.

Output

Per ciascun caso di test, stampate prima un solo intero $p$ ($p\ge 1$): il numero di coppie $(x_1,x_2)$ che sono servite in qualche riga.

Nelle successive $p$ righe, stampate quattro interi $x_1,x_2,cnt,k$ ($1\le x_1\le x_2\le 10^9$, $0\le cnt,k\le 10^9$). Il numero $cnt$ deve essere uguale al numero di righe in cui è servita la coppia $(x_1,x_2)$. Il numero $k$ deve essere uguale al numero massimo di righe consecutive in cui è servita la coppia $(x_1,x_2)$.

Tutte le coppie $(x_1,x_2)$ devono essere distinte. Ogni coppia che è servita in qualche riga deve essere stampata esattamente una volta. Potete stampare le coppie in qualsiasi ordine.

Sottoproblemi

Per un caso di test indichiamo con $w$ la larghezza del campo, cioè $w=\max_{i=1}^{n}x_i^R$, e con $h$ l'altezza del campo, cioè $h=\max_{i=1}^{n}y_i^R$.

• Se, per un test, la vostra soluzione determina in modo errato l'insieme delle coppie $(x_1,x_2)$ che sono servite in qualche riga, riceve il verdetto «Risposta errata».

• Se, in tutti i test del sottoproblema e dei sottoproblemi necessari, la soluzione:

  • determina correttamente l'insieme, ma non tutti i valori $cnt$ sono corretti, riceve il $50\%$ dei punti del sottoproblema.
  • determina correttamente l'insieme e tutti i valori $cnt$, ma non tutti i valori $k$ sono corretti, riceve il $75\%$ dei punti del sottoproblema.
  • determina correttamente l'insieme, tutti i valori $cnt$ e tutti i valori $k$, riceve il $100\%$ dei punti del sottoproblema.

Notate che, per ottenere un punteggio parziale in un sottoproblema, dovete comunque stampare dei valori $cnt$ e $k$ per ogni coppia $(x_1,x_2)$, ma non è necessario che siano corretti.

Esempi

Input 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

Output 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

Nota

Primo e secondo caso di test dell'esempio del testo.

Nel primo caso di test verranno utilizzati robot sui segmenti $(2,3,2)$, $(2,4,3)$, $(3,4,4)$. Pertanto le coppie $(2,3)$, $(2,4)$, $(3,4)$ sono servite in qualche riga, e ciascuna è servita esattamente in una riga.

Nel secondo caso di test verranno utilizzati robot sui segmenti $(2,2,1)$, $(2,4,2)$, $(2,2,3)$. Pertanto le coppie $(2,2)$, $(2,4)$ sono servite in qualche riga. La coppia $(2,2)$ è servita nelle righe $1,3$, mentre la coppia $(2,4)$ è servita nella riga $2$.

Terzo e quarto caso di test dell'esempio del testo.