背景

GESP八级真题(202506)

描述

给定⼀棵有 $n$ 个结点的 有根树，结点依次以 $1, 2, ..., n$ 编号，其中根结点的编号为 $1$ 。

⼩ $A$ 计划在这棵有根树上进⾏ $q$ 次旅⾏。在第 $i$ 次旅⾏中，⼩ A ⾸先会选定结点 $s_i$ 作为起点，并移动若⼲次。移动分为以下两种：

1. 移动⾄当前结点的⽗结点。特殊地，如果当前位于根结点，则不进⾏移动。

2. 移动⾄当前结点的所有⼦结点中 编号最⼩ 的结点。特殊地，如果当前位于叶⼦结点，则不进⾏移动。

由于移动次数可能很⼤，对于第 $i$ 次旅⾏，旅⾏中的移动将以 $k_i$ 个不为零的整数构成的序列 $a_{i,1}, a_{i,2}, ..., 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_2, ..., p_n$ ，其中 $p_i$ 表⽰结点 $i$ 的⽗结点编号。

接下来 $2q$ ⾏中的第 $2i-1$ ⾏（ $1 \le i \le q$ ）包含两个正整数 $s_i, k_i$ ，分别表⽰第 $i$ 次旅⾏的起点编号，以及移动序列的长度。第 $2i$ ⾏包含 $k_i$ 个整数 $a_{i,1}, a_{i,2}, ... , 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 \le n \le 10^5，1 \le q \le 2 \times 10^4, 1 \le p_i \le n, 1 \le s_i \le n, k_i \ge 1 且 \sum k_i \le 10^5 $。

限制

时间限制：1.0 s

空间限制：512.0 MB