Возвращаясь на базу, Джили заблудился. Он обнаружил, что тропинки впереди образуют дерево. На каждой развилке стоял указатель, но на них действовало аномальное магнитное поле, и они постоянно вращались. Жили забеспокоилась за Джили и хочет задать вам несколько вопросов. Каждый раз, по конкретному моменту времени, она спрашивает, на какой вершине Джили в конечном итоге остановился бы, если бы начал путь с самого начала.
Дано дерево с $$$n$$$ вершинами, корнем которого является вершина $$$1$$$. Вершина $$$u$$$ имеет $$$d_u$$$ дочерних вершин, отсортированных по индексам в порядке возрастания, а именно: $$$s_{u,0},\ldots,s_{u,d_u-1}$$$. Переход по каждому ребру занимает некоторое время; в частности, время, необходимое для перехода по ребру между вершиной $$$u$$$ и её родителем,равно $$$l_u$$$.
Каждая нелистовая вершина в дереве имеет указатель, указывающий на одного из его детей. Находясь в такой вершине, вы должны немедленно перейти к ребенку, на которого он указывает, и продолжать таким образом, пока не достигнете листовой вершины, где вы немедленно останавливаетесь.
Указатели меняются со временем. В момент времени $$$m$$$ указатель вершины $$$u$$$ указывает на его $$$(m\bmod d_u+1)$$$-ю дочернюю вершину, то есть на вершину $$$s_{u,m \bmod d_u}$$$.
Теперь есть $$$q$$$ запросов. В каждом запросе вам дано $$$m$$$, и вам нужно определить индекс листовой вершины, до которой вы в конечном итоге доберётесь, если начнёте с корня в момент времени $$$m$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два целых положительных числа $$$n, q$$$ ($$$1 \le n \le 5 \cdot 10^5, 1 \le q \le 10^6$$$).
Во второй строке указано $$$n-1$$$ целых положительных чисел $$$f_2,\ldots,f_n$$$ ($$$1 \le f_u \lt u$$$), где $$$f_u$$$ — индекс родителя вершины $$$u$$$.
В третьей строке указано $$$n-1$$$ целых неотрицательных чисел $$$l_2,\ldots,l_n$$$ ($$$0 \le l_u \le 10^9$$$), где $$$l_u$$$ обозначает время, необходимое для перехода по ребру между вершиной $$$u$$$ и его родителем.
Четвертая строка содержит $$$q$$$ целых неотрицательных чисел $$$m_1,\ldots,m_{q}$$$ ($$$0 \le m_i \le 10^{18}$$$), представляющих $$$q$$$ запросов.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одну строку, содержащую $$$q$$$ целых положительных чисел, представляющих ответ на каждый запрос.
23 11 110 20410 51 2 2 2 1 1 3 4 51 2 3 4 5 6 7 8 91 2 3 4 5
26 7 9 6 7
Дерево в первом наборе входных данных показано ниже.
Дерево во втором наборе входных данных показано ниже.
