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 $ .

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 $ .

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

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.