Ramazan decidió dedicarse a un negocio serio: cultivar coles.

El campo para cultivar coles es una cuadrícula infinita. En cada celda del campo se puede plantar una col.

Ramazan solo plantó una parte del campo. Planeó utilizar varias parcelas rectangulares y resultó que algunas pueden solaparse. Una celda pertenece al cultivo si está dentro de al menos uno de los rectángulos.

Formalmente, Ramazan eligió $n$ parcelas rectangulares $(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 celda $(x,y)$ contiene una col si existe al menos un rectángulo elegido $i$ ($1\le i\le n$) tal que $x_i^L\le x\le x_i^R$ e $y_i^L\le y\le y_i^R$.

En el pasado, Ramazan era programador (y ganador), por lo que decidió utilizar robots con inteligencia artificial para atender periódicamente el cultivo. Un robot puede atender un segmento horizontal arbitrario de celdas $(x_1^{robot},x_2^{robot},y^{robot})$, es decir, todas las celdas $(x,y)$ tales que $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$.

Es importante que los robots circulen únicamente por las zonas cultivadas. Ramazan comprendió que, para minimizar el número de robots, es importante utilizar segmentos horizontales que no se puedan ampliar. Ramazan utilizará un robot en el segmento de celdas $(x_1^{robot},x_2^{robot},y^{robot})$ si:

• Todas las celdas $(x,y)$ tales que $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$ pertenecen al cultivo.
• La celda $(x_1^{robot}-1,y^{robot})$ no pertenece al cultivo.
• La celda $(x_2^{robot}+1,y^{robot})$ no pertenece al cultivo.

Tu tarea es recopilar estadísticas importantes sobre los robots que trabajarán en la plantación. Diremos que el par $(x_1,x_2)$ es atendido en la fila $y$ si existe un robot que trabaja exactamente en el segmento $(x_1,x_2,y)$.

• Encuentra todos los pares $(x_1,x_2)$ que son atendidos en alguna fila.
• Para cada uno de estos pares $(x_1,x_2)$, encuentra el número de filas en las que es atendido.
• Para cada uno de estos pares $(x_1,x_2)$, encuentra el número máximo de filas consecutivas en las que es atendido. En otras palabras, encuentra el mayor número $k$ tal que existe un intervalo de $k$ filas consecutivas $[y_1,y_2]$ ($y_2-y_1+1=k$) en el que, para toda fila $y_1\le y\le y_2$, el par $(x_1,x_2)$ es atendido en la fila $y$.

Entrada

Cada prueba consta de varios casos. La primera línea contiene un entero $t$ ($1\le t\le200\,000$), el número de casos. A continuación se describen los casos.

La primera línea de cada caso contiene un único entero $n$ ($1\le n\le200\,000$), el número de parcelas rectangulares elegidas.

Las siguientes $n$ líneas contienen cuatro enteros cada una, $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$), que describen las parcelas rectangulares elegidas.

Sea $N$ la suma de $n$ sobre todos los casos de una prueba. Se garantiza que $N\le200\,000$.

Salida

Para cada caso, imprime primero un único entero $p$ ($p\ge1$), el número de pares $(x_1,x_2)$ que son atendidos en alguna fila.

En las siguientes $p$ líneas, imprime cuatro enteros $x_1,x_2,cnt,k$ por línea ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^9$). El número $cnt$ debe ser el número de filas en las que es atendido el par $(x_1,x_2)$. El número $k$ debe ser el número máximo de filas consecutivas en las que es atendido el par $(x_1,x_2)$.

Todos los pares $(x_1,x_2)$ deben ser distintos. Cada par atendido en alguna fila debe imprimirse exactamente una vez. Los pares pueden imprimirse en cualquier orden.

Subtareas

Para cada caso, sea $w$ la anchura del campo, es decir, $w=\max_{i=1}^{n}x_i^R$, y sea $h$ su altura, es decir, $h=\max_{i=1}^{n}y_i^R$.

• Si, en una prueba, tu solución encuentra incorrectamente el conjunto de pares $(x_1,x_2)$ atendidos en alguna fila, recibe el veredicto «Respuesta incorrecta».

• Si, en todas las pruebas de la subtarea y de las subtareas necesarias, la solución cumple una de las condiciones siguientes:

  • Encuentra correctamente el conjunto, pero no todos los valores $cnt$ son correctos: recibe el $50\%$ de los puntos de la subtarea.
  • Encuentra correctamente el conjunto y todos los valores $cnt$, pero no todos los valores $k$ son correctos: recibe el $75\%$ de los puntos de la subtarea.
  • Encuentra correctamente el conjunto, todos los valores $cnt$ y todos los valores $k$: recibe el $100\%$ de los puntos de la subtarea.

Ten en cuenta que, para obtener puntuación parcial en una subtarea, sigue siendo necesario imprimir algún valor de $cnt$ y $k$ para cada par $(x_1,x_2)$, aunque no es necesario que sean correctos.

Ejemplos

Entrada 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

Salida 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

Primer y segundo casos de la prueba del enunciado.

En el primer caso se utilizarán robots en los segmentos $(2,3,2)$, $(2,4,3)$ y $(3,4,4)$. Por tanto, los pares $(2,3)$, $(2,4)$ y $(3,4)$ son atendidos en alguna fila, y cada uno de ellos es atendido en exactamente una fila.

En el segundo caso se utilizarán robots en los segmentos $(2,2,1)$, $(2,4,2)$ y $(2,2,3)$. Por tanto, los pares $(2,2)$ y $(2,4)$ son atendidos en alguna fila. El par $(2,2)$ es atendido en las filas $1$ y $3$, y el par $(2,4)$ es atendido en la fila $2$.

Tercer y cuarto casos de la prueba del enunciado.