После того, как Уово услышал историю доктора Чжан, он решил спланировать свой собственный полет вокруг света.
Он уже выбрал \(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\), удовлетворяющая всем ограничениям выше.
Выходные данные
Для каждого набора входных данных, выведите YES, если существует последовательность \(b_1,\ldots, b_n\), удовлетворяющая всем ограничениям. И NO иначе. Выводить саму последовательность \(b_1,\ldots, b_n\) не требуется.
Примечание
В первом наборе входных данных все \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
NO
YES
YES
NO
|