题目描述

定义一系列分形树 $F_i$。首先给出一棵至少包含 $2$ 个点的有根树 $F_0$。

对于 $i\ge 1$，$F_i$ 由 $F_{i-1}$ 递归构造而来：找到 $F_{i-1}$ 中所有叶子组成的集合 $S$。对每个叶子 $v\in S$，用一份 $F_0$ 的拷贝替换它，并让 $v$ 对应于这份 $F_0$ 拷贝的根。

现在给定 $k$，考虑树 $F_k$。对 $F_k$ 做一次深度优先搜索：在一个点处，先递归访问最左儿子的子树，再访问第二个最左儿子的子树，依此类推。按照 DFS 首次访问点的顺序，从 $1$ 开始给所有点标号。

给出若干对顶点标号，请求出它们在 $F_k$ 中的距离。距离定义为两点之间简单路径上的边数。

图示

输入格式

首先给出树 $F_0$。

第一行包含一个整数 $n$，表示 $F_0$ 的顶点数，满足 $2\le n\le 100000$。顶点编号为 $0$ 到 $n-1$，其中 $0$ 是根。

第二行包含 $n-1$ 个整数 $p_1,p_2,\ldots,p_{n-1}$。对每个 $1\le i\le n-1$，$p_i$ 表示顶点 $i$ 在 $F_0$ 中的父亲。保证 $p_i<i$。在树中，儿子从左到右的顺序与编号从小到大的顺序一致，也就是说编号最小的儿子最靠左。

第三行包含整数 $k$，满足 $0\le k<2^{30}$。

第四行包含整数 $q$，表示询问数量，满足 $1\le q\le 100000$。

接下来 $q$ 行，每行包含两个不同整数 $a,b$，表示 $F_k$ 中两个点的 DFS 标号。保证 $a,b$ 都是合法标号，且均不超过 $2^{30}$。

输出格式

对每个询问 $(a,b)$，按输入顺序输出一行，表示 $F_k$ 中标号为 $a$ 和 $b$ 的两个点之间的距离。

输入输出样例 #1

输入 #1

4
0 1 0
1
10
1 2
1 4
1 6
1 8
1 10
5 10
6 8
9 3
7 10
8 9

输出 #1

1
3
3
2
2
6
5
5
1
1