听完张医生的故事后,窝窝决定计划自己的环球飞行。
他已经在世界地图上选择了$$$n$$$个检查点。由于地形和云层的原因,他不能飞得太高或太低。正式地,令 $$$b_i$$$ 为 Wowo 飞机在检查点 $$$i$$$ 的高度,$$$x_i^-\le b_i\le x_i^+$$$ 应该满足 $$$1$$$ 和 $$$n$$$ 之间的所有整数 $$$i$$$,其中 $$$x_i^-$$$ 和 $$$x_i^+$$$ 为给定整数。
窝窝的飞行器角度也受到限制。例如,它无法进行 $$$90$$$ 度的爬升。形式上,$$$y_i^-\le b_i-b_{i-1}\le y_i^+$$$ 对于 $$$2$$$ 和 $$$n$$$ 之间的所有整数 $$$i$$$ 应该满足,其中 $$$y_i^-$$$ 和 $$$y_i^+$$$ 是给定的整数。
最后的限制是向上钓鱼或向下钓鱼的速度。出于安全考虑,飞机应该缓慢改变角度。形式上,$$$z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$$$ 应满足 $$$3$$$ 和 $$$n$$$ 之间的所有整数 $$$i$$$,其中 $$$z_i^-$$$ 和 $$$z_i^+$$$ 为给定整数。
考虑到这些,窝窝发现检查站的高度对他来说太难选择了。请帮助wowo判断是否存在满足上述所有约束的实数序列$$$b_1, \ldots, b_n$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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}$$$) 不会改变答案。
输出
对于每个测试用例,如果存在满足约束的序列 $$$b_1,\ldots, b_n$$$ 则输出 YES,否则输出 NO。序列 $$$b_1,\ldots, b_n$$$ 不是必需的。
示例
输入 #1
4 3 0 1 0 1 0 1 1 1 1 1 -100 100 3 -967 541 -500 834 -724 669 -858 978 -964 962 -645 705 4 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 4 0 0 33 34 65 66 100 100 0 100 0 100 0 100 0 0 0 0
输出 #1
NO YES YES NO
注意
在第一个测试用例中,所有 $$$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$$$。