题目描述

小 X 有 $n$ 个正整数二元组 $(a_i, b_i)$ $(1 \leq i \leq n)$。他将会维护初始为空的可重集 $S$，并对其进行 $n$ 轮操作。第 $i$ $(1 \leq i \leq n)$ 轮操作中，他会在 $S$ 中加入 $a_i$ 个 $b_i$。

设 $m = \sum \limits_{i=1}^{n} a_i$，在所有操作结束后，小 X 会得到一个包含 $m$ 个正整数的可重集 $S$。最后他会计算 $S$ 的中位数，即 $S$ 中第 $\left\lfloor \frac{m+1}{2} \right\rfloor$ 小的数，作为他的幸运数字。

想知道小 X 幸运数字的小 Y 不知道这 $n$ 个二元组的具体数值是多少，但她得知了每个数的范围。具体地，对于每个 $1 \leq i \leq n$，小 Y 知道 $a_i \in [l_{i,1}, r_{i,1}]$ 且 $b_i \in [l_{i,2}, r_{i,2}]$。

小 Y 想知道在满足以上条件的情况下，有多少个数可能成为小 X 的幸运数字。

输入格式

从文件 lucky.in 中读入数据。

本题有多组测试数据。输入的第一行两个整数 $c, T$，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 $c = 0$。

对于每组测试数据，第一行一个整数 $n$，表示二元组的个数，接下来 $n$ 行，第 $i$ $(1 \leq i \leq n)$ 行四个整数 $l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}$，描述二元组每个数的范围。

输出格式

输出到文件 lucky.out 中。

对于每组测试数据，输出一行一个整数，表示可能的幸运数字个数。

0 4
2
1 2 1 1
1 1 2 2
2
1 1 1 2
1 1 2 3
2
1 2 1 2
2 3 3 4
4
1 2 1 4
3 4 1 2
3 4 2 3
3 4 3 4

1
2
4
3

该组样例共有 $4$ 组测试数据。 - 对于第一组测试数据，若取 $(a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)$，则得到 $S = \{1, 2\}$，其中位数为 $1$；若取 $(a_1, b_1) = (2, 1), (a_2, b_2) = (1, 2)$，则得到 $S = \{1, 1, 2\}$，其中位数为 $1$。因此仅有 $1$ 为可能计算出的中位数，因此答案为 $1$。 - 对于第二组测试数据，若取 $(a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)$，则得到 $S = \{1, 2\}$，其中位数为 1；若取 $(a_1, b_1) = (1, 2), (a_2, b_2) = (1, 3)$，则得到 $S = \{2, 3\}$，其中位数为 $2$。可以证明不存在其他可能计算出的中位数，因此答案为 $2$。 - 对于第三组测试数据，可以证明有且仅有 $1, 2, 3, 4$ 为可能计算出的中位数，因此答案为 $4$。 - 对于第四组测试数据，可以证明有且仅有 $1, 2, 3$ 为可能计算出的中位数，因此答案为 $3$。

样例 2

见选手目录下的 lucky/lucky2.in 与 lucky/lucky2.ans。

该组样例共有 $60$ 组测试数据，所有数据均满足 $n = 4$。其中测试数据 $1 \sim 20$ 满足特殊性质 AB，测试数据 $21 \sim 40$ 满足特殊性质 A。

样例 3

见选手目录下的 lucky/lucky3.in 与 lucky/lucky3.ans。

该组样例共有 $4$ 组测试数据，所有数据均满足 $n = 2\,000$。其中测试数据 $1$ 满足特殊性质 AB，测试数据 $2$ 满足特殊性质 A，测试数据 $3$ 满足特殊性质 B。

样例 4

见选手目录下的 lucky/lucky4.in 与 lucky/lucky4.ans。

该组样例共有 $2$ 组测试数据，所有数据均满足 $n = 2 \times 10^5$。其中测试数据 $1$ 满足特殊性质 A，测试数据 $2$ 满足特殊性质 B。

子任务

设 $\sum n$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试点，

• $1 \leq T \leq 400$，
• $1 \leq n \leq 2 \times 10^5$，$1 \leq \sum n \leq 6 \times 10^5$，
• $\forall 1 \leq i \leq n$，$1 \leq l_{i,1} \leq r_{i,1} \leq 10^9$，$1 \leq l_{i,2} \leq r_{i,2} \leq 10^9$。

\begin{array}{|c|c|c|c|c|} \hline \textbf{测试点编号} & n \leq & \sum n \leq & \textbf{特殊性质 }A & \textbf{特殊性质 }B \\ \hline 1 & 4 & 400 & \textbf{是} & \textbf{是} \\ \hline 2 & 4 & 400 & \textbf{是} & \textbf{否} \\ \hline 3 & 2\,000 & 10^4 & \textbf{是} & \textbf{是} \\ \hline 4 & 2\,000 & 10^4 & \textbf{是} & \textbf{否} \\ \hline 5 & 2\,000 & 10^4 & \textbf{否} & \textbf{是} \\ \hline 6 & 2\,000 & 10^4 & \textbf{否} & \textbf{否} \\ \hline 7 & 2 \times 10^5 & 6 \times 10^5 & \textbf{是} & \textbf{是} \\ \hline 8 & 2 \times 10^5 & 6 \times 10^5 & \textbf{是} & \textbf{否} \\ \hline 9 & 2 \times 10^5 & 6 \times 10^5 & \textbf{否} & \textbf{是} \\ \hline 10 & 2 \times 10^5 & 6 \times 10^5 & \textbf{否} & \textbf{否} \\ \hline \end{array}

• 特殊性质 A：$\forall 1 \leq i \leq n$，$r_{i,1}, r_{i,2} \leq n$。
• 特殊性质 B：$\forall 1 \leq i \leq n$，$l_{i,1} = r_{i,1}$。