H. Полет вокруг света
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того, как Уово услышал историю доктора Чжан, он решил спланировать свой собственный полет вокруг света.

Он уже выбрал $$$n$$$ контрольных точек на карте мира. Из-за формы рельефа и облаков, он не может лететь слишком высоко или слишком низко. Формально, пусть $$$b_i$$$ будет высота самолета Уово на контрольной точке $$$i$$$. Для всех целых $$$i$$$ между $$$1$$$ и $$$n$$$ должно выполняться $$$x_i^-\le b_i\le x_i^+$$$, где $$$x_i^-$$$ и $$$x_i^+$$$ — данные вам целые числа.

Угол полета самолета Уово тоже ограничен. Например, он не может лететь вертикально вверх под $$$90$$$ градусов. Формально, $$$y_i^-\le b_i-b_{i-1}\le y_i^+$$$ должно выполняться для всех целых $$$i$$$ между $$$2$$$ и $$$n$$$, где $$$y_i^-$$$ и $$$y_i^+$$$ — данные вам целые числа.

Последнее ограничение связано со скоростью изменения угла. Самолет должен делать это плавно из соображений безопасности. Формально, $$$z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$$$ должно выполняться для всех целых $$$i$$$ между $$$3$$$ и $$$n$$$, где $$$z_i^-$$$ и $$$z_i^+$$$ — данные вам целые числа.

Принимая во внимание все эти ограничения, Уово обнаружил, что выбрать высоты для контрольных точек слишком сложно. Помогите Уово определить, существует ли последовательность вещественных чисел $$$b_1, \ldots, b_n$$$, удовлетворяющая всем ограничениям выше.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 66\,666$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 100\,000$$$).

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i^-$$$, $$$x_i^+$$$ ($$$-10^8\le x_i^-\le x_i^+\le 10^8$$$), обозначающих нижнее и верхнее ограничение на $$$b_i$$$.

$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$y_{i+1}^-$$$, $$$y_{i+1}^+$$$ ($$$-10^8\le y_{i+1}^-\le y_{i+1}^+\le 10^8$$$), обозначающих нижнее и верхнее ограничение на $$$b_{i+1}-b_i$$$.

$$$i$$$-я из следующих $$$n-2$$$ строк содержит два целых числа $$$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}$$$) не изменит ответ.

Выходные данные

Для каждого набора входных данных, выведите YES, если существует последовательность $$$b_1,\ldots, b_n$$$, удовлетворяющая всем ограничениям. И NO иначе. Выводить саму последовательность $$$b_1,\ldots, b_n$$$ не требуется.

Пример
Входные данные
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
Выходные данные
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$$$.