Description

On the $xy$-Cartesian coordinate plane, there are $n$ axis-aligned rectangular clouds. Each cloud is represented by a 5-tuple $(x_i, y_i, w_i, h_i, d_i)$, where $(x_i, y_i)$ is the coordinate of the lower-left corner, $w_i$ is the width along the $x$-axis, $h_i$ is the length along the $y$-axis, and $d_i \in \{0, 1\}$ is the moving direction ($0$ for horizontal, $1$ for vertical). Specifically, a cloud with $d_i = 0$ moves continuously along the positive $x$-axis at a speed of 1 unit length per second, and a cloud with $d_i = 1$ moves continuously along the positive $y$-axis at a speed of 1 unit length per second.

The Führer observes that all clouds have no overlapping area at this moment. He marks this moment as time $0$. He wants to know, for any moment in $(-\infty, +\infty)$ and any single point on the plane, what is the maximum number of clouds that can simultaneously cover it. A point is covered by a cloud at some moment if and only if it lies strictly inside the rectangle occupied by the cloud at that moment (excluding the boundary).

You need to write a program to satisfy his curiosity.

Input Format

The first line contains a positive integer $T$ — the number of test cases. Then follow $T$ test cases in the format below, with no blank lines between them.

• Line 1: a positive integer $n$ — the number of clouds.
• Then $n$ lines follow: each line contains five space-separated integers $x_i$, $y_i$, $w_i$, $h_i$, and $d_i$ — describing the state of one cloud at time $0$.

Output Format

For each test case, output one line — the maximum number of clouds that can cover some point at any time.

3
1
0 0 1 1 0
3
0 -10 10 10 1
10 0 10 10 1
-10 0 10 10 0
3
0 10 10 10 1
10 20 10 10 1
10 0 10 10 0

1
2
2

Hint

In the 1st test group, at any time, any point is covered by at most one cloud.

In the 2nd test group, the following figure from left to right illustrates the situations at time 0, time 4, and time 11.

In the 3rd test group, time 0 corresponds to the situation at time 20 in the 2nd test group. In this group, during times in $(-20, 0)$, there are always 2 clouds covering the same point. Please note that the range $(-\infty, +\infty)$ includes times before time $0$.

Constraints:

For all testdata, $1 \leq T \leq 15$, $-5\times 10^8 \leq x_i, y_i \leq 5\times 10^8$, $1 \leq w_i, h_i \leq 5\times 10^8$, $d_i \in \{0, 1\}$.

Credit: https://www.luogu.org/discuss/show?postid=35727

Translated by ChatGPT 5