В этой задаче вам требуется помочь Берляндской армии организовать их систему распространения приказов.

Всего в Берляндской армии есть $$$n$$$ офицеров. Первый офицер — командующий армии, он не имеет никаких вышестоящих командующих. Любой другой офицер имеет ровно одного непосредственного командующего. Если офицер $$$a$$$ является непосредственным командующим офицера $$$b$$$, то можно сказать, что офицер $$$b$$$ непосредственный подчиненный офицера $$$a$$$.

Офицер $$$x$$$ является подчиненным (непосредственным или по цепочке) офицера $$$y$$$, если выполняется одно из следующих условий:

• офицер $$$y$$$ непосредственный командующий офицера $$$x$$$;
• непосредственный командующий офицера $$$x$$$ является подчиненным офицера $$$y$$$.

Например, на картинке ниже подчиненными офицера $$$3$$$ являются: $$$5, 6, 7, 8, 9$$$.

Структура Берляндской армии организована таким образом, что каждый офицер, кроме командующего, является подчиненным командующего армией.

Формально, Берляндская армия может быть представлена как дерево, состоящее из $$$n$$$ вершин, в котором вершина $$$u$$$ соответствует офицеру с номером $$$u$$$. Предок вершины $$$u$$$ соответствует непосредственному командующему офицера $$$u$$$. Корень (который имеет номер $$$1$$$) соответствует командующему армией.

Военное министерство Берляндии приказало вам ответить на $$$q$$$ запросов, $$$i$$$-й запрос представлен в виде $$$(u_i, k_i)$$$, где $$$u_i$$$ — это некоторый офицер, а $$$k_i$$$ — некоторое натуральное число.

Для обработки $$$i$$$-го запроса представим, как приказ, отданный офицером с номером $$$u_i$$$ распространяется по поддереву $$$u_i$$$. Этот алгоритм очень похож на DFS (depth first search, обход в глубину).

Представим, что сейчас распространяет приказ офицер с номером $$$a$$$. Офицер $$$a$$$ выбирает $$$b$$$ — одного из своих непосредственных подчиненных (то есть сына в дереве), который еще не получил приказ. Если существует несколько таких непосредственных подчиненных, тогда $$$a$$$ выбирает офицера с минимальным индексом среди них. Офицер $$$a$$$ отдает приказ офицеру $$$b$$$. После этого $$$b$$$ использует такой же самый алгоритм, чтобы распространить приказ в своем поддереве. После того, как $$$b$$$ прекращает распространять приказ, офицер $$$a$$$ выбирает следующего непосредственного подчиненного (при помощи такого же алгоритма). Когда $$$a$$$ не может выбрать непосредственного подчиненного, еще не получившего приказ, офицер $$$a$$$ прекращает распространять приказ.

Посмотрим на следующий пример:

Если офицер $$$1$$$ распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке : $$$[1, 2, 3, 5 ,6, 8, 7, 9, 4]$$$.

Если офицер $$$3$$$ распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: $$$[3, 5, 6, 8, 7, 9]$$$.

Если офицер $$$7$$$ распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: $$$[7, 9]$$$.

Если офицер $$$9$$$ распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: $$$[9]$$$.

Чтобы ответить на $$$i$$$-й запрос $$$(u_i, k_i)$$$, сформируем последовательность того, в каком порядке офицеры будут получать приказ, если $$$u_i$$$-й офицер начал его распространять. Ответом будет являться $$$k_i$$$-й элемент сформированной последовательности или -1, если в ней меньше $$$k_i$$$ элементов.

Запросы необходимо рассматривать независимо. Запрос не затрагивает следующие запросы.