A15758. Rectangle Shrinking

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of rectangles.

Each of the next $n$ lines contains four integers $u_i, l_i, d_i, r_i$ ( $1 \le u_i \le d_i \le 2$ ; $1 \le l_i \le r_i \le 10^9$ ) — the coordinates of cells located in the top-left and the bottom-right corners of the rectangle, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, first print an integer $s$ — the largest possible covered by new rectangles area. Then print $n$ lines with your solution to cover this area.

In the $i$ -th of these lines print four integers $u'_i, l'_i, d'_i, r'_i$ . If you remove the $i$ -th rectangle, print $u'_i = l'_i = d'_i = r'_i = 0$ . Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the $i$ -th rectangle, satisfying $u_i \le u'_i \le d'_i \le d_i$ ; $l_i \le l'_i \le r'_i \le r_i$ .

If there are multiple solutions, print any.

The picture in the statement illustrates the first test case.

The picture in the statement illustrates the first test case.