CF1517H.Fly Around the World

After hearing the story of Dr. Zhang, Wowo decides to plan his own flight around the world.

He already chose $n$ checkpoints in the world map. Due to the landform and the clouds, he cannot fly too high or too low. Formally, let $b_i$ be the height of Wowo's aircraft at checkpoint $i$, $x_i^-\le b_i\le x_i^+$ should be satisfied for all integers $i$ between $1$ and $n$, where $x_i^-$ and $x_i^+$ are given integers.

The angle of Wowo's aircraft is also limited. For example, it cannot make a $90$-degree climb. Formally, $y_i^-\le b_i-b_{i-1}\le y_i^+$ should be satisfied for all integers $i$ between $2$ and $n$, where $y_i^-$ and $y_i^+$ are given integers.

The final limitation is the speed of angling up or angling down. An aircraft should change its angle slowly for safety concerns. Formally, $z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$ should be satisfied for all integers $i$ between $3$ and $n$, where $z_i^-$ and $z_i^+$ are given integers.

Taking all these into consideration, Wowo finds that the heights at checkpoints are too hard for him to choose. Please help Wowo decide whether there exists a sequence of real numbers $b_1, \ldots, b_n$ satisfying all the contraints above.

在听了张博士的故事后，Wowo 决定规划自己的一次环球飞行。

他已在世界地图上选定了 $n$ 个检查点。由于地形和云层的影响，他无法飞得过高或过低。形式化地，设 $b_i$ 表示 Wowo 的飞机在第 $i$ 个检查点处的高度，则对所有介于 $1$ 到 $n$ 之间的整数 $i$，必须满足 $x_i^-\le b_i\le x_i^+$，其中 $x_i^-$ 和 $x_i^+$ 是给定的整数。

Wowo 的飞机的俯仰角也受到限制。例如，它不能进行 $90^\circ$ 的陡峭爬升。形式化地，对所有介于 $2$ 到 $n$ 之间的整数 $i$，必须满足 $y_i^-\le b_i-b_{i-1}\le y_i^+$，其中 $y_i^-$ 和 $y_i^+$ 是给定的整数。

最后的限制是俯仰角变化（即抬头或低头）的速度。出于安全考虑，飞机应缓慢改变其俯仰角。形式化地，对所有介于 $3$ 到 $n$ 之间的整数 $i$，必须满足 $z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$，其中 $z_i^-$ 和 $z_i^+$ 是给定的整数。

综合考虑上述所有限制，Wowo 发现为各检查点选定合适高度十分困难。请帮助 Wowo 判断：是否存在一个实数序列 $b_1, \ldots, b_n$ 满足上述所有约束条件。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 66\,666$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 100\,000$).

The $i$-th of the next $n$ lines contains two integers $x_i^-$, $x_i^+$ ($-10^8\le x_i^-\le x_i^+\le 10^8$) denoting the lower and upper bound of $b_i$.

The $i$-th of the next $n-1$ lines contains two integers $y_{i+1}^-$, $y_{i+1}^+$ ($-10^8\le y_{i+1}^-\le y_{i+1}^+\le 10^8$) denoting the lower and upper bound of $b_{i+1}-b_i$.

The $i$-th of the next $n-2$ lines contains two integers $z_{i+2}^-$, $z_{i+2}^+$ ($-10^8\le z_{i+2}^-\le z_{i+2}^+\le 10^8$) denoting the lower and upper bound of $(b_{i+2}-b_{i+1}) - (b_{i+1}-b_i)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

It is guaranteed that relaxing every constraint by $10^{-6}$ (i.e., decrease $x_i^-, y_i^-, z_i^-$ by $10^{-6}$ and increase $x_i^+, y_i^+, z_i^+$ by $10^{-6}$) will not change the answer.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 66\,666$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 100\,000$）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i^-$、$x_i^+$（$-10^8\le x_i^-\le x_i^+\le 10^8$），表示 $b_i$ 的下界与上界。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $y_{i+1}^-$、$y_{i+1}^+$（$-10^8\le y_{i+1}^-\le y_{i+1}^+\le 10^8$），表示 $b_{i+1}-b_i$ 的下界与上界。

接下来的 $n-2$ 行中，第 $i$ 行包含两个整数 $z_{i+2}^-$、$z_{i+2}^+$（$-10^8\le z_{i+2}^-\le z_{i+2}^+\le 10^8$），表示 $(b_{i+2}-b_{i+1}) - (b_{i+1}-b_i)$ 的下界与上界。

保证所有测试用例的 $n$ 值之和不超过 $200\,000$。

保证将每个约束放宽 $10^{-6}$（即：将所有 $x_i^-, y_i^-, z_i^-$ 减小 $10^{-6}$，并将所有 $x_i^+, y_i^+, z_i^+$ 增大 $10^{-6}$）不会改变答案。

For each test case, output YES if a sequence $b_1,\ldots, b_n$ satisfying the constraints exists and NO otherwise. The sequence $b_1,\ldots, b_n$ is not required.

对于每个测试用例，如果存在满足约束条件的序列 $b_1,\ldots, b_n$，则输出 YES；否则输出 NO。无需输出序列 $b_1,\ldots, b_n$ 本身。

In the first test case, all $b_i$'s are in $[0,1]$. Because of the constraints $1=y_2^-\le b_2-b_1\le y_2^+=1$, $b_2-b_1$ must be $1$. So $b_2=1$ and $b_1=0$ must hold. Then by $1=y_3^-\le b_3-b_2\le y_3^+=1$, $b_3$ equals $2$. This contradicts the constraint of $b_3\le 1$. So no solution exists.

In the second test case, we can let all $b_i$'s be $0$.

In the third test case, one possible solution is $b_1=0$, $b_2=1/3$, $b_3=2/3$, $b_4=1$.

在第一个测试用例中，所有 $b_i$ 均位于区间 $[0,1]$ 内。由于约束条件 $1=y_2^-\le b_2-b_1\le y_2^+=1$，可知 $b_2-b_1$ 必须等于 $1$，因此必有 $b_2=1$ 且 $b_1=0$。接着由 $1=y_3^-\le b_3-b_2\le y_3^+=1$ 可得 $b_3=2$，但这与约束 $b_3\le 1$ 矛盾。因此该问题无解。

在第二个测试用例中，可令所有 $b_i$ 均为 $0$。

在第三个测试用例中，一个可行解为 $b_1=0$，$b_2=1/3$，$b_3=2/3$，$b_4=1$。