G. Поиск дурака и запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача использует определения из задачи E. Однако она не требует того же ответа.

Существует бинарное дерево из $$$n+1$$$ вершин ($$$n$$$ нечетное), с вершинами, пронумерованными $$$0,1,\ldots,n$$$. На каждой вершине может быть написана не более одной буквы, и изначально на всех вершинах ничего не написано. Корень дерева — это вершина $$$0$$$.

В дереве вершина $$$0$$$ является родителем вершины $$$1$$$, в то время как у всех остальных вершин либо $$$2$$$ ребёнка, либо $$$0$$$.

Боб заблудился в одной из вершин дерева и хочет выбраться из дерева, добравшись до вершины $$$0$$$. Это очень легко для большинства людей с обычным здравым смыслом. Однако, поскольку Боб — дурак, он придумал новый способ обхода дерева, введя «Поиск дурака».

Когда Боб находится на вершине $$$v$$$ ($$$1 \le v \le n$$$), его движение определяется следующим образом:

  • Если вершина $$$v$$$ является листом, Боб всегда движется к родителю $$$v$$$; в противном случае он проверяет следующие условия.
  • Если на вершине $$$v$$$ ничего не написано, Боб пишет 'L' на вершине $$$v$$$ и движется к левому ребенку $$$v$$$;
  • Если на вершине $$$v$$$ написано 'L', Боб перезаписывает её на 'R' и движется к правому ребенку $$$v$$$;
  • Если на вершине $$$v$$$ написано 'R', Боб стирает её и движется к родителю $$$v$$$.

Бобу требуется ровно $$$1$$$ секунда, чтобы перейти к соседней вершине, так что Боб потратит ровно $$$x$$$ секунд на выполнение $$$x$$$ перемещений.

Доказано, что независимо от того, с какой вершины начинает Боб, он может добраться до вершины $$$0$$$ за конечное (хотя и возможно необъяснимо большое) время. Мы не знаем, кто это доказал; конечно, это не мог быть Боб, но это определенно доказано.

Вам предлагается ответить на $$$q$$$ запросов следующего вида:

  • $$$v\;k$$$: Предполагая, что Боб начал с вершины $$$v$$$, определите, на какой вершине находится Боб после выполнения ровно $$$k$$$ движений ($$$1 \le v \le n$$$).

Для каждого запроса пусть $$$T_v$$$ — это время, необходимое для достижения вершины $$$0$$$ из вершины $$$v$$$. Тогда гарантируется, что $$$k \lt T_v$$$ для каждого запроса.

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

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

Первая строка каждого набора содержит целые числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 300\,001$$$, $$$1 \le q \le 400\,000$$$, $$$n$$$ нечетное).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$, обозначающие детей вершины $$$i$$$ ($$$0 \le l_i,r_i \le n$$$).

Для каждой вершины, если $$$l_i=r_i=0$$$, это означает, что у вершины нет детей. В противном случае $$$l_i$$$ и $$$r_i$$$ — это левые и правые дети вершины $$$i$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$v_j$$$ и $$$k_j$$$, обозначающие $$$j$$$-й запрос ($$$1 \le v_j \le n$$$, $$$0 \le k_j \color{red}{ \lt } \min(10^9+7,T_{v_j})$$$).

Гарантируется, что ввод определяет корректное бинарное дерево, удовлетворяющее условиям, указанным в задаче.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$300\,001$$$.

Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превышает $$$400\,000$$$.

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

Для каждого набора входных данных выведите ответы на $$$q$$$ запросов на отдельной строке.

Пример
Входные данные
3
1 1
0 0
1 0
5 5
2 3
0 0
4 5
0 0
0 0
3 6
3 8
3 11
4 7
5 8
7 7
2 3
4 5
0 0
6 7
0 0
0 0
0 0
1 9
2 18
3 11
3 12
3 13
5 7
7 17
Выходные данные
1
2 3 5 2 1
2 2 1 3 1 2 4
Примечание

В первом примере есть только две вершины, вершина $$$0$$$ и вершина $$$1$$$. Очевидно, что Боб будет находиться на вершине $$$1$$$, когда $$$0$$$ движений было выполнено после того, как Боб начал с вершины $$$1$$$.

Во втором примере дерево задано следующим образом.

Бобу требуется $$$14$$$ секунд, чтобы достичь вершины $$$0$$$ из вершины $$$3$$$. Движения следующие:

$$$$$$3 \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} 5 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{L}} \color{red}{2} \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{R}} \color{red}{3} \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} \color{red}{5} \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{X}} 0$$$$$$

Здесь буквы над стрелками обозначают букву на вершине перед движением к соседней вершине, где $$$\mathtt{X}$$$ обозначает, что ничего не написано.

Как показано красным, это означает, что:

  • Боб находится на вершине $$$2$$$, когда $$$6$$$ движений было выполнено после того, как Боб начал с вершины $$$3$$$;
  • Боб находится на вершине $$$3$$$, когда $$$8$$$ движений было выполнено после того, как Боб начал с вершины $$$3$$$;
  • Боб находится на вершине $$$5$$$, когда $$$11$$$ движений было выполнено после того, как Боб начал с вершины $$$3$$$.