返回基地时,吉莉迷路了。他发现前面的路形成了一棵树。每一个岔路口,都有一个路标,但这些路标受到异常磁场的影响,不断旋转。芝莉开始担心吉莉,想问你几个问题。每次,在给定的特定时刻,他都会询问如果从头开始,吉莉最终会停在哪个节点。
给你一棵有$$$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
注意
第一个测试用例中的树如下所示。
第二个测试用例中的树如下所示。