树上旅行

题目描述

给定一棵有 \(n\) 个结点的有根树，结点依次以 \(1, 2, \ldots, n\) 编号，其中根结点的编号为 \(1\)。小 A 计划在这棵有根树上进行 \(q\) 次旅行。在第 \(i\) 次旅行中，小 A 首先选定结点 \(s\) 作为起点，并移动若干次。移动分为以下两种：

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

由于移动次数可能很大，对于第 \(i\) 次旅行，旅行中的移动将以 \(k\) 个不为零的整数构成的序列表示。对于序列中的每个数 \(a\)，若 \(a > 0\) 则代表进行 \(a\) 次第一种移动；若 \(a < 0\) 则代表进行 \(|a|\) 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。

输入格式

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

第二行，\(n-1\) 个整数，其中第 \(i\) 个表示结点 \(i+1\) 的父结点编号。

接下来 \(q\) 行，每行先给出两个正整数 \(s, k\)，分别表示第 \(i\) 次旅行的起点编号以及移动序列的长度；随后紧跟 \(k\) 个整数 \(a\)，表示移动序列。

输出格式

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

样例

输入样例 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

数据范围

对于所有测试点，保证 \(1 \le n \le 10^5\)，\(1 \le q \le 10^5\)，\(1 \le |a| \le 10^5\)，结点编号与父结点编号合法（构成以 \(1\) 为根的有根树）。（数据范围由题面字体缺字重建，取保守范围）