题目描述

千里白金雪满天　烽火江山起狼烟　分手竟兵刃相见

1941.7.

苏联军队出乎意料的反抗力量、前线德军的补给困难 —— 元首 Adolf 望着天空的云层陷入沉思……

在 $xy$-直角坐标平面的天空中，有 $n$ 片四边平行于坐标轴的矩形云朵。每一片云由一个五元组 $(x_i, y_i, w_i, h_i, d_i)$ 表示，其中 $(x_i, y_i)$ 为云左下角顶点的坐标，$w_i$ 表示云在 $x$ 轴方向的宽度，$h_i$ 表示云在 $y$ 轴方向的长度，$d_i \in \{0, 1\}$ 为云的移动方向（$0$ 为横向，$1$ 为纵向）。具体来说，满足 $d_i = 0$ 的云沿 $x$ 轴正方向以每秒 $1$ 长度单位的速率不断移动，而满足 $d_i = 1$ 的云沿 $y$ 轴正方向以每秒 $1$ 长度单位的速率不断移动。

元首发现，所有的云在此时没有重叠的面积。他将这个时刻记作时刻 $0$。他想知道，对于 $(-\infty, +\infty)$ 中的任意时刻和平面上的任意一个点，最多可以同时被多少片云覆盖。一个点在某时刻被一朵云覆盖当且仅当这个点位于该时刻云朵所处矩形的内部（不含边界）。

你需要编写程序帮助元首满足他的好奇心。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$ —— 数据的组数。接下来包含 $T$ 组数据，格式如下，数据间没有空行。

• 第 $1$ 行：一个正整数 $n$ —— 云朵的数量。
• 接下来 $n$ 行：每行五个空格分隔的整数 $x_i$、$y_i$、$w_i$、$h_i$ 和 $d_i$ —— 描述一朵云在时刻 $0$ 的状态。

输出格式

输出到标准输出。

对于每组数据输出一行 —— 在任意时刻，覆盖平面上任意一个点的云朵数目的最大值。

样例

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

第 $1$ 组数据中，任意时刻的任意一个点至多被惟一的一片云覆盖。

第 $2$ 组数据中，下图从左至右分别示意时刻 $0$、时刻 $4$、时刻 $11$ 的情形。

第 $3$ 组数据中，时刻 $0$ 对应第 $2$ 组数据时刻 $20$ 的情形。在该组数据中，$(-20, 0)$ 内的时刻均有 $2$ 片云覆盖同一个点。请注意考察范围 $(-\infty, +\infty)$ 包含时刻 $0$ 之前的时间段。

数据范围与提示

子任务

对于所有数据，有 $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\}$。

“Dann soll die Armee eben kehrt machen!”

题面与史实无关。

提示

最大输入约为 50 MiB，请注意程序在读入上的耗时哦。

来自 CodePlus 2018 3 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/吕时清　命题/吕时清　验题/丁子钧
Git Repo：https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。