Руби только что получила место стажера на ферме Фермера Джона, победив в соревновании по программированию! В обязанности Руби входит обслуживание персикового дерева Фермера Джона — дерева, состоящего из \(n\) вершин, с корнем в вершине \(1\). В каждой вершине изначально содержится \(a_i = 0\) персиков. Могут происходить два вида событий:
- Событие роста в вершине \(x\): Руби должна выбрать либо родителя \(x\), либо любую вершину в поддереве \(x\), и увеличить количество персиков в ней на единицу.
- Событие сбора урожая в вершине \(x\): Руби должна выбрать одну вершину, которая находится в поддереве \(x\), и уменьшить количество содержащихся в ней персиков на единицу. Обратите внимание, что это не тот же набор вершин, что и в событии роста.
Обратите внимание, поддерево вершины
\(x\) включает в себя саму вершину
\(x\).
Руби также дан массив \(b\) длины \(n\). Персиковое дерево считается здоровым, если \(a_i \ge b_i\) для каждой вершины \(i\).
Руби предлагается выполнить \(q\) операций двух типов:
- 1 x v — Выполнить \(v\) событий роста на вершине \(x\). Руби не обязательно выбирать одну и ту же вершину для увеличения в каждом событии роста.
- 2 x v — Выполнить \(v\) событий сбора урожая на вершине \(x\). Руби не обязательно выбирать одну и ту же вершину для уменьшения в каждом событии сбора урожая.
Для каждого префикса операций она просит вас определить, может ли она выполнить эти операции в некотором порядке так, чтобы получившееся (после всех этих операций) персиковое дерево было здоровым. Обратите внимание, что Руби не может выполнять событие сбора урожая, которое сделает некоторое \(a_i\) отрицательным.
Каждый префикс операций независим, то есть для данной операции Руби может выбрать разные вершины для выполнения событий на каждом префиксе, содержащем эту операцию.
Выходные данные
Для каждого набора входных данных выведите \(q\) строк. Строка \(i\) должна содержать «YES», если Руби может сделать персиковое дерево здоровым после выполнения операций \(1, 2, \ldots, i\) в любом порядке. В противном случае она должна содержать «NO».
Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительные ответы.
Примечание
Для префикса, содержащего операции \(1, 2, \ldots, 5\) в первом примере, Руби может выполнять операции в следующем порядке:
- Руби выполняет операцию \(2\) и решает увеличить \(a_4\) на \(9\) и \(a_5\) на \(8\).
- Руби выполняет операцию \(1\) и решает увеличить \(a_1\) на \(5\), \(a_3\) на \(2\), \(a_6\) на \(4\) и \(a_8\) на \(3\).
- Руби выполняет операцию \(3\) и решает увеличить \(a_2\) на \(7\).
- Руби выполняет операцию \(4\) и решает уменьшить \(a_2\) на \(1\).
- Руби выполняет операцию \(5\) и решает увеличить \(a_7\) на \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
8 8
1 1 1 4 3 6 6
5 6 2 9 8 4 1 3
1 3 14
1 4 17
1 2 7
2 2 1
1 6 1
2 1 1000000
1 4 999999
1 3 1
10 20
1 1 1 2 5 2 4 7 2
311353 270334 74853 385085 315501 183346 234819 417314 103862 429437
1 1 837541
1 10 933876
1 1 565958
1 4 791455
2 3 85054
2 3 440978
1 4 981040
1 5 68522
2 1 858305
2 4 184308
1 4 905081
2 8 519626
2 2 269090
1 1 43016
2 2 517644
1 5 355792
1 9 319241
2 10 125447
2 10 523890
1 10 241045
|
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
|