Description

小黄今天一觉睡醒，发现自己这辈子可能发生的所有事情被记录在一个流程树上，自己经历过或未来可能将要经历的重大决策变成了选择支，自己可以通过读档来到达任意一个选择支上，进行不同的选择，来进行不同的人生。

``我当 galgame 男主？真的假的。''小黄立刻读档回到过去，开始体验不同的人生。在这个过程中，小黄发现有些选择支可以只有一个选项，例如小黄的人生明明问了小黄是否要打 acm，却没有不打的选项。

由于可以读档回到选择支来体验不同的人生，小黄这辈子的走向从线性变成了树形，每个选择支位置相当于一个节点，做出不同的选择相当于进入这个节点的不同子树。小黄通过流程树可以看见，自己的人生总共有 $n$ 个选择支，且从第一次选择开始，无论如何选择，这辈子最多不会经历超过 $1000$ 个选择支。

小黄想要进行 $q$ 次询问，每次询问中，小黄站在编号 $a_i$ 的选择支上，想要知道这个选择支上未来可能经历的选择支中从近到远第 $m_i$ 个选择支距离有多远。

Format

Input

第一行一个整数 $n\ (1 \leq n \leq 10^5)$，表示小黄树形人生中选择支的数量。

第二行有 $n-1$ 个整数 $b_1, b_2, \cdots, b_{n-1}\ (0 \leq b_i \leq n-1)$，$b_i$ 表示编号为 $i$ 的选择支的父节点，其中根节点即小黄这辈子第一个选择支的编号为 $0$。

第三行有一个正整数 $q\ (1 \leq q \leq 10^6)$，表示询问的次数。

接下来 $q$ 行，每行两个整数 $a_i, m_i\ (0 \leq a_i \leq n-1, 0 \leq m_i \leq10^6)$，表示询问时所在的选择支和询问的远近。

Output

对于每个询问输出一行，每行一个整数表示距离。如果选择支 $a_i$ 未来可能经历的选择支不足 $m_i$ 个，则输出 $114514$。

Samples

8
0 1 1 3 3 3 6
3
1 4
2 3
3 4

2
114514
2

Note

第一个样例中的第一个询问 ， 距离点 $1$ 第 $1$ 远的节点为 $2,3$ ， 第 $3,4,5$ 远的点为 $4,5,6$ ，它们到点 $1$ 的距离为 $2$ 因此答案为 $2$ 。第二个询问中 ， 节点 $2$ 之后没有子节点了 ， 因此输出 $114514$ 。

Limitation

1s, 1024KiB for each test case.