树上旅⾏

题目描述

给定⼀棵有 个结点的有根树，结点依次以 编号，其中根结点的编号为 。 ⼩ A 计划在这棵有根树上进⾏ 次旅⾏。在第 次旅⾏中，⼩ A ⾸先会选定结点 作为起点，并移动若⼲次。移动 分为以下两种：

1. 移动⾄当前结点的⽗结点。特殊地，如果当前位于根结点，则不进⾏移动。
2. 移动⾄当前结点的所有⼦结点中编号最⼩的结点。特殊地，如果当前位于叶⼦结点，则不进⾏移动。 由于移动次数可能很⼤，对于第 次旅⾏，旅⾏中的移动将以 个不为零的整数构成的序列 表 ⽰。对于 ，若 则代表进⾏ 次第⼀种移动；若 则代表进⾏ 次第⼆种移动。根据给出的序 列从左⾄右完成所有移动后，⼩ A 所在的结点即是旅⾏的终点。 给定每次旅⾏的起点与移动序列，请你求出旅⾏终点的结点编号。

输入格式

第⼀⾏，两个正整数 ，分别表⽰有根树的结点数量，以及旅⾏次数。 第⼆⾏， 个整数 ，其中 表⽰结点 的⽗结点编号。 接下来 ⾏中的第 ⾏（ ）包含两个正整数 ，分别表⽰第 次旅⾏的起点编号，以及移动序列 的长度。第 ⾏包含 个整数 ，表⽰移动序列。

输出格式

输出共 ⾏，第 ⾏包含⼀个整数，表⽰第 次旅⾏终点的结点编号。

样例输入 #1

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

样例输出 #1

4
1
4
2

样例输入 #2

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

样例输出 #2

1
7
1

数据范围

⼦任务编号 测试点占⽐ 特殊性质 1 % 保证 为 或 2 % 仅包含第⼀种移动 3 % 仅包含第⼆种移动 4 % - 对于所有测试点，保证 ， ， ， ， 且 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。