背景

特别适合初学者，^_^

题目描述

在返回基地的路上，Jily 迷路了。
他发现前方的道路形成了一棵树。
在每个岔路口都有一个路标，但是这些路标受到异常磁场的影响，会随着时间不断旋转。

Bileo 很担心 Jily，于是他想问你若干个问题。
每次给定一个具体的出发时刻，他想知道：如果 Jily 从起点出发，最终会停在哪个节点。

给定一棵有 $n$ 个节点的树，根节点为 $1$。

对于节点 $u$，它有 $d_u$ 个儿子。
这些儿子按照节点编号从小到大排序，依次记为：

从节点 $u$ 的父亲走到节点 $u$ 需要花费 $l_u$ 的时间。

每个非叶子节点都有一个路标，路标会指向它的某一个儿子。
当你到达一个非叶子节点时，必须立刻沿着当前路标指向的儿子继续走。
不断重复这个过程，直到到达一个叶子节点为止。
到达叶子节点后，会立即停止。

路标会随着时间变化。

在时刻 $m$，节点 $u$ 的路标会指向它的第 $(m \bmod d_u + 1)$ 个儿子，也就是节点：

现在有 $q$ 次询问。
每次询问给定一个时刻 $m$，你需要回答：如果从根节点 $1$ 在时刻 $m$ 出发，最终会到达哪个叶子节点。

注意，经过一条边会消耗时间，因此到达下一个节点时，当前时间会增加。

格式

输入

每个测试点包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数

接下来是每组测试数据的描述。

每组测试数据第一行包含两个正整数 $n,q$，分别表示节点数量和询问数量。

第二行包含 $n-1$ 个正整数 $f_2,f_3,\ldots,f_n$

其中 $f_u$ 表示节点 $u$ 的父亲 $1 \leq f_u < u$

第三行包含 $n-1$ 个非负整数 $l_2,l_3,\ldots,l_n$

其中 $l_u$ 表示从节点 $u$ 的父亲走到节点 $u$ 需要花费的时间。

第四行包含 $q$ 个非负整数$m_1,m_2,\ldots,m_q$

表示每次询问的出发时刻

保证所有测试数据中 $n$ 的总和不超过：$5 \cdot 10^5$

保证所有测试数据中 $q$ 的总和不超过：$10^6$

$1 \leq t \leq 10^4$

$1 \leq n \leq 5 \cdot 10^5$

$1 \leq q \leq 10^6$

$0 \leq l_u \leq 10^9$

$0 \leq m_i \leq 10^{18}$

输出

对于每组测试数据，输出一行，包含 $q$ 个正整数。

第 $i$ 个整数表示第 $i$ 次询问最终到达的叶子节点编号。

样例

2
3 1
1 1
10 20
4
10 5
1 2 2 2 1 1 3 4 5
1 2 3 4 5 6 7 8 9
1 2 3 4 5

2
6 7 9 6 7

限制

2秒，1024MiB，每个测试点。