树上旅行

时间限制：1.0 s 内存限制：512.0 MB

题目描述

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

1. 移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
2. 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。 由于移动次数可能很大，对于第i次旅行，旅行中的移动将以ki个不为零的整数构成的序列a{i,1},a{i,2},...,a{i,ki}表示。对于a{ij}，若a{ij}>0则代表进行a{ij}次第一种移动；若a{ij}<0则代表进行-a{ij}次第二种移动。根据给出的序列从左至右完成所有移动后，小A所在的结点即是旅行的终点。 给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

输入格式

第一行，两个正整数n,q，分别表示有根树的结点数量，以及旅行次数。 第二行，n-1个整数p_2,p_3,...,p_n，其中p_i表示结点i的父结点编号。 接下来2q行中的第2i-1行（1<=i<=q）包含两个正整数s_i,k_i，分别表示第i次旅行的起点编号，以及移动序列的长度。第2i行包含ki个整数a{i,1},a{i,2},...,a{i,k_i}，表示移动序列。

输出格式

输出共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

输入样例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 ≤ n ≤ 1e5，1 ≤ q ≤ 2e4，1 ≤ p_i ≤ n，1 ≤ s_i ≤ n，k_i ≥1且∑ki ≤1e5，1 ≤ |a{i,j}| ≤n。