Background

Translated from ROI 2024 D1T4.

Ramazan decided to start an important business—growing cabbages. The field for growing cabbages is an infinite grid. Each grid cell can contain one cabbage. Ramazan only planted cabbages on part of the field. He plans to use several rectangular areas, and these rectangles may intersect. If a grid cell lies inside at least one rectangle, then this cell is considered planted with cabbages.

More precisely, Ramazan chose $n$ rectangles with coordinates $(x_{L_i}, y_{L_i}, x_{R_i}, y_{R_i})$ (where $x_{L_i} \le x_{R_i}$, $y_{L_i} \le y_{R_i}$, $1 \le i \le n$). If there exists at least one rectangle $i$ ($1 \le i \le n$) such that $x_{L_i} \le x \le x_{R_i}$ and $y_{L_i} \le y \le y_{R_i}$, then the grid cell $(x, y)$ is considered planted with cabbages.

Ramazan used to be a programmer (and also a prize winner), so he decided to use AI robots to periodically maintain the planting. One robot can serve any horizontal segment $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$, that is, all grid cells $(x, y)$ such that $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ and $y = y_{\text{robot}}$.

Importantly, a robot can move only inside the planted area. He understands that, to minimize the number of robots, he needs to use horizontal segments that cannot be extended further. Ramazan will use a robot to work on the segment $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$ if the following conditions hold:

• All grid cells $(x, y)$ such that $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ and $y = y_{\text{robot}}$ belong to the planted area.
• The grid cell $(x_{\text{robot}_1} - 1, y_{\text{robot}})$ does not belong to the planted area.
• The grid cell $(x_{\text{robot}_2} + 1, y_{\text{robot}})$ does not belong to the planted area.

Problem Description

You need to collect statistics about how robots work on the planted area. If there exists a robot that works exactly on the grid segment $(x_1, x_2, y)$, we say that the pair $(x_1, x_2)$ is served on row $y$. More precisely, you need to:

• Find all pairs $(x_1, x_2)$ that are served on some row.
• For each such pair $(x_1, x_2)$, find the number of rows on which it is served.
• For each such pair $(x_1, x_2)$, find the maximum number of consecutive rows on which it is served. In other words, find the maximum value $k$ such that there exists a consecutive row interval $[y_1, y_2]$ (where $y_2 - y_1 + 1 = k$) such that on every row $y_1 \le y \le y_2$, the pair $(x_1, x_2)$ is served.

Input Format

The input contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 200000$), the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 200000$), the number of rectangles.

The next $n$ lines each contain four integers $x_{L_i}$, $y_{L_i}$, $x_{R_i}$, $y_{R_i}$ ($1 \le x_{L_i} \le x_{R_i} \le 10^9$, $1 \le y_{L_i} \le y_{R_i} \le 10^9$), describing one rectangle.

Let $N$ be the sum of $n$ over all test cases. It is guaranteed that $N \le 200000$.

Output Format

For each test case, first output an integer $p$ ($p \ge 1$), the number of pairs $(x_1, x_2)$ that are served on some row. Then output $p$ lines, each containing four integers $x_1$, $x_2$, $cnt$, $k$ ($1 \le x_1 \le x_2 \le 10^9$, $0 \le cnt, k \le 10^9$). Here, $cnt$ is the number of rows on which this pair $(x_1, x_2)$ is served, and $k$ is the maximum number of consecutive rows on which it is served.

Each pair $(x_1, x_2)$ must be different. Every pair $(x_1, x_2)$ that is served on some row must be output exactly once. The output order can be arbitrary.

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

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

Hint

In the first test case, robots serve the following segments: $(2, 3, 2)$, $(2, 4, 3)$, and $(3, 4, 4)$. Therefore, the pairs $(2, 3)$, $(2, 4)$, and $(3, 4)$ are served on some row, and each pair is served on only one row.

In the second test case, robots serve the following segments: $(2, 2, 1)$, $(2, 4, 2)$, and $(2, 2, 3)$. Therefore, the pairs $(2, 2)$ and $(2, 4)$ are served on some row. The pair $(2, 2)$ is served on rows $1$ and $3$, while the pair $(2, 4)$ is served on row $2$.

Below are the pictures for the third and fourth test cases.

• If your program finds the wrong set of pairs $(x_1, x_2)$ that are served on some row, the test will receive zero points.
• If your program:
  • Can correctly find this set, but not all $cnt$ are correct, the test will receive $50\%$ of the points.
  • Can correctly find this set and all $cnt$, but not all $k$ are correct, the test will receive $75\%$ of the points.
  • Can correctly find this set, all $cnt$, and all $k$, the test will receive $100\%$ of the points.

Please note that if you want to get partial points, you still need to output some $cnt$ and $k$ values for each pair $(x_1, x_2)$, but they do not have to all be correct.

Translated by ChatGPT 5