Yandex 拥有一套定义明确的从属结构，表现为一棵带有指定根节点的树。$N$ 名员工中的每一位都在树中对应一个顶点，并拥有一个整数标识号 $v$ ($0 \le v < N$)。根节点是标识号为 $0$ 的顶点。

由于这个组织树逐年壮大，Yandex 需要树领域算法和数据结构方面的专家。作为测试，所有候选人都被要求完成以下这项既无意义又残酷的任务。

给定一棵员工树，其中每个人的上司（公司负责人除外）都是已知的，你需要依次回答 $M$ 个查询。每个查询包含两个顶点 $u$ 和 $v$。

假设 $u$ 和 $v$ 之间的最短路径为 $p_1, p_2, \dots, p_k$，其中 $p_1 = u$ 且 $p_k = v$。为了找到查询 $(u, v)$ 的答案，你需要计算以下总和：

$$\sum_{w=0}^{N-1} \min(d(w, p_1), \dots, d(w, p_k)) \cdot w$$

其中 $d(w, p_i)$ 是顶点 $w$ 和 $p_i$ 之间的边距离，并且——没错，你理解得对——求和中的 $\min(\dots)$ 项乘以了顶点标识号本身。

输入格式

输入的第一行包含一个整数 $N$，表示树中顶点的数量 ($2 \le N \le 100\,000$)。 下一行包含 $N-1$ 个以空格分隔的整数，其中第 $i$ 个数（从 $1$ 开始计数）是顶点 $i$ 的父节点标识号。保证给定的图是一棵以 $0$ 为根的树。 第三行包含一个整数 $M$，表示查询的数量 ($0 \le M \le 100\,000$)。 接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$：表示需要计算上述总和的顶点标识号对。

输出格式

对于输入中的每个查询，在单独的一行中输出一个整数，即该查询的答案。

样例

输入 1

10
0 0 1 1 1 1 1 3 1
3
1 6
5 0
8 7

输出 1

48
47
28