F2. Метрополитен в Омске (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между простой и сложной версией состоит в том, что в этой версии $$$u$$$ может принимать любые возможные значения.

Как известно, Омск — столица Берляндии. Как и в любой столице, в Омске есть хорошо развитая система метрополитена. Метрополитен Омска представляет из себя некоторое количество станций, соединённых туннелями, причём между любыми двумя станциями есть ровно один путь, проходящий по каждому из туннелей не более одного раза. Иными словами, метрополитен представляет собой дерево.

Для развития метрополитена и привлечения жителей в Омске используется следующая система. Каждая станция имеет свой вес $$$x \in \{-1, 1\}$$$. Если станция имеет вес $$$-1$$$, то при посещении станции с жителя Омска взимается плата в $$$1$$$ бурль. Если же вес станции равен $$$1$$$, то житель Омска вознаграждается $$$1$$$-м бурлем.

Пока что есть только одна станция с номером $$$1$$$ и весом $$$x = 1$$$. Каждый день происходит одно из следующих событий:

  • К станции с номером $$$v_i$$$ присоединяется новая станция с весом $$$x$$$, и ей присваивается номер, на единицу больший количества уже существующих станций.
  • Лёша, живущий в Омске, задаётся вопросом: существует ли подотрезок$$$\dagger$$$ (возможно, пустой) пути между вершинами $$$u$$$ и $$$v$$$ такой, что, проехав по нему, можно заработать ровно $$$k$$$ бурлей (если $$$k < 0$$$, то это означает, что на проезд придётся потратить $$$k$$$ бурлей). Иначе говоря, Лёшу интересует, существует ли такой подотрезок пути, что сумма весов вершин в нем равна $$$k$$$. Обратите внимание, что подотрезок может быть пустым, и тогда сумма равна $$$0$$$.

Вы являетесь другом Лёши, поэтому Ваша задача — ответить на вопросы Лёши.

$$$\dagger$$$Подотрезок — непрерывная последовательность элементов.

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

В первой строке находится число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных дано число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество событий.

Далее следует $$$n$$$ строк, описывающих события. В $$$i$$$-й строке возможен один из вариантов:

  • Сначала идёт символ «+» (без кавычек), затем два числа $$$v_i$$$ и $$$x_i$$$ ($$$x_i \in \{-1, 1\}$$$, также гарантируется, что вершина с номером $$$v_i$$$ существует). В этом случае к станции с номером $$$v_i$$$ присоединяется новая станция с весом $$$x_i$$$.
  • Сначала идёт символ «?» (без кавычек), а затем три числа $$$u_i$$$, $$$v_i$$$ и $$$k_i$$$ ($$$-n \le k_i \le n$$$). Гарантируется, что вершины с номерами $$$u_i$$$ и $$$v_i$$$ существуют. В этом случае необходимо определить, существует ли подотрезок (возможно, пустой) пути между станциями $$$u_i$$$ и $$$v_i$$$ с суммой весов ровно $$$k_i$$$.

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

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

Для каждого вопроса Лёши выведите «Yes» (без кавычек), если описанный в условии подотрезок существует, иначе выведите «No» (без кавычек).

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

Примеры
Входные данные
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
Входные данные
1
7
+ 1 -1
+ 2 -1
+ 2 1
+ 3 -1
? 5 2 2
? 3 1 -1
? 5 4 -3
Выходные данные
NO
YES
YES
Примечание

Пояснение к первому примеру.

Ответ на второй вопрос «Yes», так как существует путь $$$1$$$.

В четвертом вопросе мы можем снова выбрать путь $$$1$$$.

В пятом запросе ответ «Yes», так как есть путь $$$1-3$$$.

В шестом запросе мы можем выбрать пустой путь, так как сумма весов на нем равна $$$0$$$.

Нетрудно показать, что нет путей, удовлетворяющих первому и третьему запросу.