Рамазан decidiu dedicar-se a um negócio sério: o cultivo de couves.

O campo para cultivar couves é uma grelha infinita de células. Pode ser plantada uma cabeça de couve em cada célula.

Рамазан plantou apenas parte do campo. Planeou utilizar várias regiões retangulares e verificou que algumas delas podem sobrepor-se. Uma célula pertence à plantação se estiver em pelo menos um dos retângulos.

Formalmente, Рамазан escolheu $n$ regiões retangulares $(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$). A célula $(x,y)$ contém couve se existir pelo menos um retângulo escolhido $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$.

No passado, Рамазан era programador (e vencedor), pelo que decidiu utilizar robôs com inteligência artificial para tratar periodicamente a plantação. Um robô pode servir uma região horizontal arbitrária de células $(x_1^{robot},x_2^{robot},y^{robot})$, ou seja, todas as células $(x,y)$ tais que $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$.

É importante que os robôs circulem apenas pelas regiões plantadas. Percebeu que, para minimizar o número de robôs, é importante utilizar regiões horizontais que não possam ser ampliadas. Рамазан utilizará um robô na região de células $(x_1^{robot},x_2^{robot},y^{robot})$ se:

• Todas as células $(x,y)$ tais que $x_1^{robot}\le x\le x_2^{robot}$ e $y=y^{robot}$ pertencerem à plantação;
• A célula $(x_1^{robot}-1,y^{robot})$ não pertencer à plantação;
• A célula $(x_2^{robot}+1,y^{robot})$ não pertencer à plantação.

A sua tarefa é recolher estatísticas importantes sobre os robôs que trabalharão na plantação. Diremos que o par $(x_1,x_2)$ é servido na linha $y$ se existir um robô que trabalha exatamente na região $(x_1,x_2,y)$.

• Encontre todos os pares $(x_1,x_2)$ que são servidos em alguma linha.
• Para cada um desses pares $(x_1,x_2)$, encontre o número de linhas em que é servido.
• Para cada um desses pares $(x_1,x_2)$, encontre o número máximo de linhas consecutivas em que é servido. Por outras palavras, encontre o maior número $k$ tal que exista um intervalo de $k$ linhas consecutivas $[y_1,y_2]$ ($y_2-y_1+1=k$) em que, para qualquer linha $y_1\le y\le y_2$, o par $(x_1,x_2)$ seja servido na linha $y$.

Entrada

Cada teste consiste em vários casos de teste. A primeira linha contém um inteiro $t$ ($1\le t\le 200\,000$), o número de casos de teste. Seguem-se as descrições dos casos de teste.

A primeira linha de cada caso de teste contém um único inteiro $n$ ($1\le n\le 200\,000$), o número de regiões retangulares escolhidas.

As $n$ linhas seguintes contêm, cada uma, quatro inteiros $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$), que descrevem as regiões retangulares escolhidas.

Seja $N$ a soma de $n$ sobre todos os casos de teste de um teste. É garantido que $N\le 200\,000$.

Saída

Para cada caso de teste, comece por imprimir um único inteiro $p$ ($p\ge 1$), o número de pares $(x_1,x_2)$ que são servidos em alguma linha.

Nas $p$ linhas seguintes, imprima quatro inteiros $x_1$, $x_2$, $cnt$, $k$ ($1\le x_1\le x_2\le 10^9$, $0\le cnt,k\le 10^9$). O número $cnt$ deve ser igual ao número de linhas em que o par $(x_1,x_2)$ é servido. O número $k$ deve ser igual ao número máximo de linhas consecutivas em que o par $(x_1,x_2)$ é servido.

Todos os pares $(x_1,x_2)$ devem ser distintos. Cada par servido em alguma linha deve ser impresso exatamente uma vez. Os pares podem ser impressos em qualquer ordem.

Subtarefas

Para um caso de teste, seja $w$ a largura do campo, isto é, $w=\max_{i=1}^{n}x_i^R$, e $h$ a altura do campo, isto é, $h=\max_{i=1}^{n}y_i^R$.

• Se, num teste, a sua solução encontrar incorretamente o conjunto dos pares $(x_1,x_2)$ servidos em alguma linha, receberá o veredito «Resposta incorreta».

• Se, em todos os testes da subtarefa e das subtarefas necessárias, a solução:

  • Encontrar corretamente o conjunto, mas nem todos os valores de $cnt$ estiverem corretos, recebe $50\%$ dos pontos da subtarefa.
  • Encontrar corretamente o conjunto e todos os valores de $cnt$, mas nem todos os valores de $k$ estiverem corretos, recebe $75\%$ dos pontos da subtarefa.
  • Encontrar corretamente o conjunto, todos os valores de $cnt$ e todos os valores de $k$, recebe $100\%$ dos pontos da subtarefa.

Note que, para obter pontos parciais numa subtarefa, ainda é necessário imprimir algum valor de $cnt$ e de $k$ para cada par $(x_1,x_2)$, embora esses valores não tenham de estar corretos.

Exemplos

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

Saída 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

Primeiro e segundo casos de teste do teste do enunciado

No primeiro caso de teste, serão utilizados robôs nas regiões $(2,3,2)$, $(2,4,3)$ e $(3,4,4)$. Assim, os pares $(2,3)$, $(2,4)$ e $(3,4)$ são servidos em alguma linha, cada um deles em exatamente uma linha.

No segundo caso de teste, serão utilizados robôs nas regiões $(2,2,1)$, $(2,4,2)$ e $(2,2,3)$. Assim, os pares $(2,2)$ e $(2,4)$ são servidos em alguma linha. O par $(2,2)$ é servido nas linhas $1$ e $3$, e o par $(2,4)$ é servido na linha $2$.

Terceiro e quarto casos de teste do teste do enunciado