某公司的员工关系按层级结构组织。公司共有 $n$ 名员工，每名员工有一个从 $1$ 到 $n$ 的唯一编号，主管的编号为 $1$。除主管外，每名员工恰有一名直属上司。员工 $i$ 的直属上司编号为 $p_i$，且 $p_i<i$。

若 $p_x=y$，则员工 $x$ 是员工 $y$ 的第 $1$ 级下属。对于 $k>1$，若员工 $p_x$ 是员工 $y$ 的第 $k-1$ 级下属，则员工 $x$ 是员工 $y$ 的第 $k$ 级下属。

公司主管有机会派一些员工参加进修课程。为此，他决定选择两个数 $L$ 和 $R$，派所有编号 $i$ 满足 $L \le i \le R$ 的员工参加课程。

在选择 $L$ 和 $R$ 之前，主管收到了公司员工的 $m$ 个愿望。第 $j$ 个愿望由两个数 $u_j$ 和 $k_j$ 表示，意思是员工 $u_j$ 希望派自己的一名第 $k_j$ 级下属参加课程。为了节省费用，主管希望选择 $L$ 和 $R$，使参加进修的员工人数尽可能少，同时满足所有愿望。

请编写程序，根据公司的上下级关系和员工愿望，求出两个数 $L$ 和 $R$，使派所有编号从 $L$ 到 $R$（包含两端）的员工参加进修课程后，所有愿望都得到满足，且参加进修的员工人数尽可能少。若有多个最优数对 $L,R$，应找到其中 $L$ 最小的一对。

输入格式

输入文件第一行包含公司员工人数 $n$（$2 \le n \le 200\,000$）。第二行包含 $n-1$ 个数 $p_2,p_3,\ldots,p_n$（$1 \le p_i<i$），表示各员工直属上司的编号。

第三行包含员工愿望的数量 $m$。

接下来 $m$ 行描述员工愿望，每行包含两个整数 $u_j,k_j$（$1 \le u_j<n$，$1 \le k_j<n$；保证员工 $u_j$ 至少有一名第 $k_j$ 级下属）。

输出格式

输出所求的两个数 $L$ 和 $R$。若有多个最优数对 $(L,R)$，输出其中 $L$ 最小的一对。

样例

输入格式 1

7
1 1 2 2 3 3
3
1 1
3 1
1 2

输出格式 1

3 6

说明

编号为 $3$、$4$、$5$ 和 $6$ 的员工将参加进修。员工 $3$ 是员工 $1$ 的第 $1$ 级下属，员工 $4$ 是员工 $1$ 的第 $2$ 级下属，员工 $6$ 是员工 $3$ 的第 $1$ 级下属。

子任务

只有通过该子任务及其所需子任务的全部测试，才能获得该子任务的分数。

最终评测结果信息

可以请求获知每个子任务的分数。