Это простая версия задачи. Единственное отличие между простой и сложной версией состоит в том, что в этой версии для всех вопросов \(u = 1\).
Как известно, Омск — столица Берляндии. Как и в любой столице, в Омске есть хорошо развитая система метрополитена. Метрополитен Омска представляет из себя некоторое количество станций, соединённых туннелями, причём между любыми двумя станциями есть ровно один путь, проходящий по каждому из туннелей не более одного раза. Иными словами, метрополитен представляет собой дерево.
Для развития метрополитена и привлечения жителей в Омске используется следующая система. Каждая станция имеет свой вес \(x \in \{-1, 1\}\). Если станция имеет вес \(-1\), то при посещении станции с жителя Омска взимается плата в \(1\) бурль. Если же вес станции равен \(1\), то житель Омска вознаграждается \(1\)-м бурлем.
Пока что есть только одна станция с номером \(1\) и весом \(x = 1\). Каждый день происходит одно из следующих событий:
- К станции с номером \(v_i\) присоединяется новая станция с весом \(x\), и ей присваивается номер, на единицу больший количества уже существующих станций.
- Лёша, живущий в Омске, задаётся вопросом: существует ли подотрезок\(\dagger\) (возможно, пустой) пути между вершинами \(u\) и \(v\) такой, что, проехав по нему, можно заработать ровно \(k\) бурлей (если \(k < 0\), то это означает, что на проезд придётся потратить \(k\) бурлей). Иначе говоря, Лёшу интересует, существует ли такой подотрезок пути, что сумма весов вершин в нем равна \(k\). Обратите внимание, что подотрезок может быть пустым, и тогда сумма равна \(0\).
Вы являетесь другом Лёши, поэтому Ваша задача — ответить на вопросы Лёши.
\(\dagger\)Подотрезок — непрерывная последовательность элементов.
Выходные данные
Для каждого вопроса Лёши выведите «Yes» (без кавычек), если описанный в условии подотрезок существует, иначе выведите «No» (без кавычек).
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
Пояснение к первому примеру.
Ответ на второй вопрос «Yes», так как существует путь \(1\).
В четвертом вопросе мы можем снова выбрать путь \(1\).
В пятом запросе ответ «Yes», так как есть путь \(1-3\).
В шестом запросе мы можем выбрать пустой путь, так как сумма весов на нем равна \(0\).
Нетрудно показать, что нет путей, удовлетворяющих первому и третьему запросу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0
|
NO
YES
NO
YES
YES
YES
|
|
2
|
1
10
+ 1 -1
+ 1 -1
+ 3 1
+ 3 -1
+ 3 1
? 1 6 -1
? 1 6 2
? 1 2 0
? 1 5 -2
? 1 4 3
|
YES
NO
YES
YES
NO
|