H. Лучший стажер фермера Джона
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Peaches...
⠀

Руби только что получила место стажера на ферме Фермера Джона, победив в соревновании по программированию! В обязанности Руби входит обслуживание персикового дерева Фермера Джона — дерева, состоящего из $$$n$$$ вершин, с корнем в вершине $$$1$$$. В каждой вершине изначально содержится $$$a_i = 0$$$ персиков. Могут происходить два вида событий:

  1. Событие роста в вершине $$$x$$$: Руби должна выбрать либо родителя $$$x$$$, либо любую вершину в поддереве $$$x$$$, и увеличить количество персиков в ней на единицу.
  2. Событие сбора урожая в вершине $$$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$$$ отрицательным.

Каждый префикс операций независим, то есть для данной операции Руби может выбрать разные вершины для выполнения событий на каждом префиксе, содержащем эту операцию.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — размер дерева и количество операций.

Вторая строка содержит $$$n - 1$$$ целых чисел $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$) — родителей вершин.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^6$$$) — минимальное количество персиков, необходимое каждой вершине для того, чтобы персиковое дерево считалось здоровым.

Следующие $$$q$$$ строк описывают операции, которые будет выполнять Руби. Каждая строка содержит три целых числа $$$t$$$, $$$x$$$ и $$$v$$$ ($$$1 \le t \le 2$$$, $$$1 \le x \le n$$$, $$$1 \le v \le 10^6$$$). Если $$$t = 1$$$, это означает, что Руби должна выполнить $$$v$$$ событий роста на вершине $$$x$$$. Если $$$t = 2$$$, это означает, что Руби должна выполнить $$$v$$$ событий урожая на вершине $$$x$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, и сумма $$$q$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк. Строка $$$i$$$ должна содержать «YES», если Руби может сделать персиковое дерево здоровым после выполнения операций $$$1, 2, \ldots, i$$$ в любом порядке. В противном случае она должна содержать «NO».

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительные ответы.

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

Для префикса, содержащего операции $$$1, 2, \ldots, 5$$$ в первом примере, Руби может выполнять операции в следующем порядке:

  1. Руби выполняет операцию $$$2$$$ и решает увеличить $$$a_4$$$ на $$$9$$$ и $$$a_5$$$ на $$$8$$$.
  2. Руби выполняет операцию $$$1$$$ и решает увеличить $$$a_1$$$ на $$$5$$$, $$$a_3$$$ на $$$2$$$, $$$a_6$$$ на $$$4$$$ и $$$a_8$$$ на $$$3$$$.
  3. Руби выполняет операцию $$$3$$$ и решает увеличить $$$a_2$$$ на $$$7$$$.
  4. Руби выполняет операцию $$$4$$$ и решает уменьшить $$$a_2$$$ на $$$1$$$.
  5. Руби выполняет операцию $$$5$$$ и решает увеличить $$$a_7$$$ на $$$1$$$.