开始: 2025-07-03 17:40:00

暑期训练赛02

结束: 2025-07-03 20:30:00
当前  2025-07-17 19:26:50  类型: IOI  状态: 已经结束 

P5. 树上旅行
描述

给定一棵有 n 个结点的 **有根树**,结点依次以 1,2,\dots,n 编号,其中根结点的编号为 1

小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先选定结点 s_i 作为起点,并移动若干次。移动分为以下两种:

    1. 移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。

    2. 移动至当前结点的所有子结点中**编号最小**的结点。特殊地,如果当前位于叶子结点,则不进行移动。

由于移动次数可能很大,对于第 i 次旅行,旅行中的移动以 k_i 个不为零的整数构成的序列 a_{i,1}, a_{i,2}, \dots, a_{i,k_i} 表示。对 a_{i,j},若 a_{i,j} > 0 则代表进行 a_{i,j} 次第一种移动;若 a_{i,j} < 0 则代表进行 -a_{i,j} 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的**终点**。

给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。


输入

第一行,两个正整数 n, q,分别表示有根树的结点数量,以及旅行次数。

第二行,n-1 个整数 p_2, p_3, \dots, p_n,其中 p_i 表示结点 i 的父结点编号。

接下来 2q 行中的第 2i-1 行(1 \leq i \leq q)包含两个正整数 s_i, k_i,分别表示第 i 次旅行的起点编号,以及移动序列的长度。第 2i 行包含 k_i 个整数 a_{i,1}, a_{i,2}, \dots, a_{i,k_i},表示移动序列。


输出

输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。

样例

输入

5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1

输出

4
1
4
2

输入

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

输出

1
7
1
提示

对于所有测试点,保证:

- 1 \leq n \leq 10^5

- 1 \leq q \leq 2 \times 10^4

- 1 \leq p_i \leq n

- 1 \leq s_i \leq n

- k_i \geq 1\sum k_i \leq 10^5

- 1 \leq |a_{i,j}| \leq n

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交