树上旅行

题目描述

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

小 A 计划在这棵有根树上进行 $q$ 次旅行。在第 $i$ 次旅行中，小 A 首先会选定结点 $s_{i}$ 作为起点，并移动若干次。移动

分为以下两种：

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

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

由于移动次数可能很大，对于第 $i$ 次旅行，旅行中的移动将以 $k_{i}$ 个不为零的整数构成的序列 $a_{i,1},a_{i,2},\ldots,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},...,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},\ldots,a_{i,k_i}$，表示移动序列。

输出格式

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

输入样例 1

15 421 1 2 233 341 -1 -152 561 -1 1 -1 175 881 1 1 -1 -1 -1 -1 -195 310-1 -1 1

输出样例 1

14213442

输入样例 2

18 325 4 2 1 3 6 638 14858 268 -878 388 -8 8

输出样例 2

112731

数据范围

子任务编号	测试点占比	$n$	$q$	$\sum k_i$	特殊性质
1	20%	$\le100$	$\le100$	$\le1000$	保证 $a_{i,j}$ 为 $1$ 或 $-1$
2	20%	$\le10^4$	$\le10^4$	$\le4\times10^4$	仅包含第一种移动
3	20%	$\le10^4$	$\le10^4$	$\le4\times10^4$	仅包含第二种移动
4	40%	$\le10^5$	$\le2\times10^4$	$\le10^5$	-

对于所有测试点，保证 $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\le |a_{i,j}|\le n$。