Ramazan a décidé de se lancer dans une activité sérieuse : la culture du chou.

Le champ destiné à cette culture est une grille infinie. On peut planter un chou dans chaque case du champ.

Ramazan n'a planté qu'une partie du champ. Il prévoyait d'utiliser plusieurs parcelles rectangulaires, mais certaines d'entre elles peuvent se chevaucher. Une case appartient aux plantations si elle se trouve dans au moins l'un de ces rectangles.

Formellement, Ramazan a choisi $n$ parcelles rectangulaires $(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 case $(x,y)$ contient un chou s'il existe au moins un rectangle choisi $i$ ($1\le i\le n$) tel que $x_i^L\le x\le x_i^R$ et $y_i^L\le y\le y_i^R$.

Autrefois, Ramazan était programmeur (et gagnant), et il a donc décidé d'utiliser des robots dotés d'intelligence artificielle pour entretenir régulièrement les plantations. Un robot peut s'occuper d'un segment horizontal quelconque de cases $(x_1^{robot},x_2^{robot},y^{robot})$, c'est-à-dire de toutes les cases $(x,y)$ telles que $x_1^{robot}\le x\le x_2^{robot}$ et $y=y^{robot}$.

Il est essentiel que les robots ne circulent que dans les plantations. Il a compris que, pour minimiser le nombre de robots, il fallait utiliser des segments horizontaux qui ne peuvent pas être agrandis. Ramazan utilisera un robot sur le segment de cases $(x_1^{robot},x_2^{robot},y^{robot})$ si :

• Toutes les cases $(x,y)$ telles que $x_1^{robot}\le x\le x_2^{robot}$ et $y=y^{robot}$ appartiennent aux plantations ;
• La case $(x_1^{robot}-1,y^{robot})$ n'appartient pas aux plantations ;
• La case $(x_2^{robot}+1,y^{robot})$ n'appartient pas aux plantations.

Votre tâche consiste à recueillir des statistiques importantes sur les robots qui travailleront dans la plantation. On dit que la paire $(x_1,x_2)$ est desservie dans la rangée $y$ s'il existe un robot travaillant exactement sur le segment $(x_1,x_2,y)$.

• Trouvez toutes les paires $(x_1,x_2)$ qui sont desservies dans au moins une rangée.
• Pour chacune de ces paires $(x_1,x_2)$, trouvez le nombre de rangées dans lesquelles elle est desservie.
• Pour chacune de ces paires $(x_1,x_2)$, trouvez le nombre maximal de rangées consécutives dans lesquelles elle est desservie. Autrement dit, trouvez le plus grand nombre $k$ tel qu'il existe un intervalle de $k$ rangées consécutives $[y_1,y_2]$ ($y_2-y_1+1=k$) et que, pour toute rangée $y_1\le y\le y_2$, la paire $(x_1,x_2)$ soit desservie dans la rangée $y$.

Entrée

Chaque test comprend plusieurs jeux de données. La première ligne contient un entier $t$ ($1\le t\le 200000$), le nombre de jeux de données. Les descriptions des jeux de données suivent.

La première ligne de chaque jeu de données contient un unique entier $n$ ($1\le n\le 200000$), le nombre de parcelles rectangulaires choisies.

Les $n$ lignes suivantes contiennent chacune quatre entiers $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$), décrivant les parcelles rectangulaires choisies.

Notons $N$ la somme des $n$ sur tous les jeux de données d'un test. On garantit que $N\le 200000$.

Sortie

Pour chaque jeu de données, affichez d'abord un unique entier $p$ ($p\ge 1$), le nombre de paires $(x_1,x_2)$ desservies dans au moins une rangée.

Sur les $p$ lignes suivantes, affichez quatre entiers $x_1,x_2,cnt,k$ ($1\le x_1\le x_2\le 10^9$, $0\le cnt,k\le 10^9$). Le nombre $cnt$ doit être égal au nombre de rangées dans lesquelles la paire $(x_1,x_2)$ est desservie. Le nombre $k$ doit être égal au nombre maximal de rangées consécutives dans lesquelles cette paire est desservie.

Toutes les paires $(x_1,x_2)$ doivent être distinctes. Chaque paire desservie dans au moins une rangée doit être affichée exactement une fois. Les paires peuvent être affichées dans n'importe quel ordre.

Sous-tâches

Pour un jeu de données, notons $w$ la largeur du champ, soit $w=\max_{i=1}^{n}x_i^R$, et $h$ sa hauteur, soit $h=\max_{i=1}^{n}y_i^R$.

• Si, pour un test, votre solution trouve incorrectement l'ensemble des paires $(x_1,x_2)$ desservies dans au moins une rangée, elle reçoit le verdict « Réponse incorrecte ».

• Si, dans tous les tests de la sous-tâche et des sous-tâches requises, la solution :

  • trouve correctement l'ensemble, mais certaines valeurs $cnt$ sont incorrectes, elle reçoit 50 % des points de la sous-tâche ;
  • trouve correctement l'ensemble et toutes les valeurs $cnt$, mais certaines valeurs $k$ sont incorrectes, elle reçoit 75 % des points de la sous-tâche ;
  • trouve correctement l'ensemble, toutes les valeurs $cnt$ et toutes les valeurs $k$, elle reçoit 100 % des points de la sous-tâche.

Notez que, pour obtenir des points partiels dans une sous-tâche, vous devez tout de même afficher des valeurs $cnt$ et $k$ pour chaque paire $(x_1,x_2)$, même si elles ne sont pas nécessairement correctes.

Exemples

Entrée 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

Sortie 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

Remarque

Premier et deuxième jeux de données du test de l'énoncé

Dans le premier jeu de données, les robots seront utilisés sur les segments $(2,3,2)$, $(2,4,3)$ et $(3,4,4)$. Les paires $(2,3)$, $(2,4)$ et $(3,4)$ sont donc desservies dans au moins une rangée, chacune étant desservie dans exactement une rangée.

Dans le deuxième jeu de données, les robots seront utilisés sur les segments $(2,2,1)$, $(2,4,2)$ et $(2,2,3)$. Les paires $(2,2)$ et $(2,4)$ sont donc desservies dans au moins une rangée. La paire $(2,2)$ est desservie dans les rangées $1$ et $3$, et la paire $(2,4)$ dans la rangée $2$.

Troisième et quatrième jeux de données du test de l'énoncé