CF2223C.Zhily and Signpost

While returning to the base, Jily lost his way. He found that the paths ahead formed a tree. At every fork in the road, there was a signpost, but these signposts were affected by an anomalous magnetic field and kept rotating. Zhily became worried about Jily and wants to ask you several questions. Each time, given a specific moment, he asks which node Jily would eventually stop at if he started from the beginning.

You are given a tree with $n$ nodes, rooted at $1$. Node $u$ has $d_u$ children, sorted by node index in increasing order, namely $s_{u,0},\ldots,s_{u,d_u-1}$. It takes some time to cross each edge; specifically, the time needed to cross the edge between node $u$ and its parent is $l_u$.

Each non-leaf node in the tree has a signpost pointing to one of its children. When you are at such a node, you must immediately move to the child it points to, continuing in this way until you reach a leaf node, where you stop immediately.

The signposts change over time. At time $m$, the signpost of node $u$ points to its $(m\bmod d_u+1)$-th child, that is, node $s_{u,m \bmod d_u}$.

There are now $q$ queries. In each query, you are given $m$, and you need to determine the index of the leaf node you will eventually reach if you start from the root at time $m$.

在返回基地的路上，Jily 迷路了。他发现前方的道路构成了一棵树。在每个岔路口都有一块指示牌，但这些指示牌受到异常磁场的影响而持续旋转。Zhily 担心 Jily 的安危，因此想向你提出若干问题：每次给定一个特定时刻，询问若 Jily 从起点（树根）出发，最终会停在哪一个节点上。

你将得到一棵含 $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$ 开始行进，最终抵达的叶节点的编号是多少。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two positive integers $n,q$ ($1 \le n \le 5 \cdot 10^5,1 \le q \le 10^6$).

The second line contains $n-1$ positive integers $f_2,\ldots,f_n$ ($1 \le f_u \lt u$), where $f_u$ denotes the index of the parent of node $u$.

The third line contains $n-1$ non-negative integers $l_2,\ldots,l_n$ ($0 \le l_u \le 10^9$), where $l_u$ denotes the time needed to cross the edge between node $u$ and its parent.

The fourth line contains $q$ non-negative integers $m_1,\ldots,m_{q}$ ($0 \le m_i \le 10^{18}$), representing the $q$ queries.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, output one line containing $q$ positive integers, representing the answer to each query.

对于每个测试用例，输出一行包含 $q$ 个正整数，表示每个查询的答案。

The tree in the first test case is shown below.

If you start at time $4$, then at that moment the signpost of node $1$ points to node $2$. You will arrive at node $2$ at time $14$ and stop there.

The tree in the second test case is shown below.

If you start at time $3$, then at that moment the signpost of node $1$ points to node $2$. You will arrive at node $2$ at time $4$. At that moment, the signpost of node $2$ points to node $4$, so you will arrive at node $4$ at time $7$. At that moment, the signpost of node $4$ points to node $9$, so you will arrive at node $9$ at time $15$ and stop there.

第一个测试用例中的树如下图所示。

若你在时刻 $4$ 出发，则此时节点 $1$ 的路标指向节点 $2$。你将在时刻 $14$ 到达节点 $2$ 并在此停止。

第二个测试用例中的树如下图所示。

若你在时刻 $3$ 出发，则此时节点 $1$ 的路标指向节点 $2$。你将在时刻 $4$ 到达节点 $2$。此时，节点 $2$ 的路标指向节点 $4$，因此你将在时刻 $7$ 到达节点 $4$。此时，节点 $4$ 的路标指向节点 $9$，因此你将在时刻 $15$ 到达节点 $9$ 并在此停止。