Рамазан 決定從事一項正經生意：種植高麗菜。
種植高麗菜的田地是一個無限大的方格網。每個格子都可以種一顆高麗菜。
Рамазан 只種了田地的一部分。他計畫使用幾個長方形區域，結果發現其中一些可能重疊。若格子位於至少一個長方形內，該格子就屬於種植區域。
形式上，Рамазан 選擇了 $n$ 個長方形區域 $(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$）。若存在至少一個選定的長方形 $i$（$1\le i\le n$），使得 $x_i^L\le x\le x_i^R$ 且 $y_i^L\le y\le y_i^R$，格子 $(x,y)$ 就有高麗菜。
Рамазан 以前是程式設計師（也是優勝者），因此他決定使用具有人工智慧的機器人定期照料種植區域。一個機器人可以負責任意的水平格子區間 $(x_1^{robot},x_2^{robot},y^{robot})$，也就是所有滿足 $x_1^{robot}\le x\le x_2^{robot}$ 且 $y=y^{robot}$ 的格子 $(x,y)$。
機器人只能在種植區域行駛，這一點很重要。他明白，為了讓機器人的數量最少，需要使用無法再擴展的水平區間。Рамазан 會在格子區間 $(x_1^{robot},x_2^{robot},y^{robot})$ 使用機器人，如果：
- 所有滿足 $x_1^{robot}\le x\le x_2^{robot}$ 且 $y=y^{robot}$ 的格子 $(x,y)$ 都屬於種植區域；
- 格子 $(x_1^{robot}-1,y^{robot})$ 不屬於種植區域；
- 格子 $(x_2^{robot}+1,y^{robot})$ 不屬於種植區域。
你的任務是收集將在農場工作的機器人的重要統計資料。若存在一個機器人恰好負責區間 $(x_1,x_2,y)$，我們就稱數對 $(x_1,x_2)$ 在第 $y$ 列被服務。
- 找出所有在某一列被服務的數對 $(x_1,x_2)$。
- 對於每個這樣的數對 $(x_1,x_2)$，求它被服務的列數。
- 對於每個這樣的數對 $(x_1,x_2)$，求它被服務的最大連續列數。換句話說，求最大的數 $k$，使得存在由 $k$ 個連續列組成的區間 $[y_1,y_2]$（$y_2-y_1+1=k$），對所有 $y_1\le y\le y_2$ 的列，數對 $(x_1,x_2)$ 都在第 $y$ 列被服務。
輸入格式
每個測試包含多組輸入資料。第一行給定一個整數 $t$（$1\le t\le200\,000$），表示資料組數。接下來是各組資料的描述。
每組資料的第一行給定一個整數 $n$（$1\le n\le200\,000$），表示選定的長方形區域數量。
接下來 $n$ 行，每行給定四個整數 $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$），描述選定的長方形區域。
以 $N$ 表示同一測試中所有資料組的 $n$ 之和。保證 $N\le200\,000$。
輸出格式
對每組資料，先輸出一個整數 $p$（$p\ge1$），表示在某一列被服務的數對 $(x_1,x_2)$ 的數量。
接下來 $p$ 行，每行輸出四個整數 $x_1,x_2,cnt,k$（$1\le x_1\le x_2\le10^9$，$0\le cnt,k\le10^9$）。$cnt$ 必須等於數對 $(x_1,x_2)$ 被服務的列數。$k$ 必須等於數對 $(x_1,x_2)$ 被服務的最大連續列數。
所有數對 $(x_1,x_2)$ 必須互不相同。每個在某一列被服務的數對都必須恰好輸出一次。可以按任意順序輸出數對。
子任務
對一組資料，以 $w$ 表示田地的寬度，即 $w=\max_{i=1}^n x_i^R$；以 $h$ 表示田地的高度，即 $h=\max_{i=1}^n y_i^R$。
| 子任務 | 分數 | 限制： $n,N$ | 限制： $w,h$ | 額外限制 | 必要子任務 |
|---|---|---|---|---|---|
| $1$ | $4$ | $n=1$ | |||
| $2$ | $8$ | $h=1$ | |||
| $3$ | $8$ | $n\le30$, $N\le3000$ | $w,h\le10$ | $t\le100$ | 範例 |
| $4$ | $4$ | $w,h\le5000$, $\sum wh\le25\cdot10^6$ | 範例, $3$ | ||
| $5$ | $8$ | $N\le3000$ | 範例, $3$ | ||
| $6$ | $4$ | $N\le10\,000$ | 範例, $3,5$ | ||
| $7$ | $8$ | 所有 $[x_i^L,x_i^R]$ 相交 | $1$ | ||
| $8$ | $8$ | $y_i^L=1$ | $2$ | ||
| $9$ | $8$ | 長方形互不相交 | $1$ | ||
| $10$ | $8$ | 對所有 $1\le i,j\le n$ 及所有 $y\in[y_i^L,y_i^R]\cap[y_j^L,y_j^R]$，都有 $[x_i^L,x_i^R]\nsubseteq[x_j^L,x_j^R]$ | $1,9$ | ||
| $11$ | $8$ | 所有區間 $[x_i^L,x_i^R+1]$ 要麼互相包含，要麼不相交 | $1$ | ||
| $12$ | $8$ | $N\le50\,000$ | 範例, $3,5\text{–}6$ | ||
| $13$ | $8$ | $N\le100\,000$ | 範例, $3,5\text{–}6,12$ | ||
| $14$ | $8$ | $N\le200\,000$ | 範例, $1\text{–}13$ |
- 如果你的解答在某個測試中錯誤地求出在某一列被服務的數對 $(x_1,x_2)$ 的集合，就會得到「答案錯誤」的判定。
如果在該子任務及其必要子任務的所有測試中，解答：
- 正確求出集合，但並非所有 $cnt$ 都正確，則得到該子任務分數的 $50\%$；
- 正確求出集合及所有 $cnt$，但並非所有 $k$ 都正確，則得到該子任務分數的 $75\%$；
- 正確求出集合、所有 $cnt$ 及所有 $k$，則得到該子任務分數的 $100\%$。
請注意，即使是為了取得子任務的部分分數，仍須為每個數對 $(x_1,x_2)$ 輸出某些 $cnt$ 和 $k$ 的值，但不必是正確的值。
範例
輸入格式 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
輸出格式 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
說明
題目中的測試的第一組與第二組輸入資料
第一組資料會在區間 $(2,3,2)$、$(2,4,3)$、$(3,4,4)$ 使用機器人。因此，數對 $(2,3)$、$(2,4)$、$(3,4)$ 在某一列被服務，且每個數對都恰好在一列被服務。
第二組資料會在區間 $(2,2,1)$、$(2,4,2)$、$(2,2,3)$ 使用機器人。因此，數對 $(2,2)$、$(2,4)$ 在某一列被服務。數對 $(2,2)$ 在第 $1,3$ 列被服務，數對 $(2,4)$ 在第 $2$ 列被服務。
題目中的測試的第三組與第四組輸入資料