结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某林场沿山设有 $n$ 个哨所，编号 $1$ 到 $n$，其中 $1$ 号为总指挥部。除总指挥部外，每个哨所有唯一上级；$i$ 号哨所（$i \ge 2$）的上级编号为 $p_i$，两者之间由一条长度为 $w_i$ 的林间道路直接相连。从任意哨所出发，沿上级关系逐级上行，有限步内必能到达总指挥部。

部分哨所设有补给站，1 号总指挥部必设补给站。巡护员的回撤任务规定如下：从哨所 $u$ 出发，沿上级链逐级回撤至哨所 $v$（保证 $v$ 在 $u$ 的上级链上且 $v \ne u$），全程须划分为若干段；每段连续行进的距离不得超过 $L$（全场统一给定），且除出发点 $u$ 与终点 $v$ 外，中途只可在补给站落脚——即每一段的两端必须是补给站、$u$ 或 $v$。

请你为每次任务求出完成回撤所需的最少段数；若按规程无论如何都无法完成回撤，输出 $-1$。

输入格式

从文件 trek.in 中读入数据。

• 第一行三个整数 $n, q, L$；
• 第二行 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示 $i$ 号哨所的上级编号；
• 第三行 $n-1$ 个整数 $w_2, w_3, \dots, w_n$，其中 $w_i$ 表示 $i$ 号哨所到其上级的道路长度；
• 第四行 $n$ 个整数 $s_1, s_2, \dots, s_n$，$s_i = 1$ 表示 $i$ 号哨所设有补给站，$s_i = 0$ 表示未设；
• 接下来 $q$ 行，每行两个整数 $u, v$，表示一次从 $u$ 回撤到 $v$ 的任务。

输出格式

输出到文件 trek.out 中。

输出 $q$ 行，每行一个整数，表示对应任务的最少段数；无法完成时输出 $-1$。

样例

6 4 5
1 2 3 4 5
3 2 4 1 2
1 0 1 0 1 0
6 4
6 2
5 3
4 1

1
3
1
2

7 4 5
1 1 2 2 3 3
2 3 2 4 7 1
1 1 0 1 0 0 0
5 1
6 1
7 3
4 2

2
-1
1
1

样例 2 解释

第一次任务从 $5$ 号回撤到 $1$ 号：$5$ 到 $1$ 的距离为 $4+2=6$，超过 $L=5$，必须分段。$5$ 与 $1$ 之间的补给站只有 $2$ 号；按 $5 \to 2 \to 1$ 行进，两段距离分别为 $4$ 与 $2$，均不超过 $5$，共 $2$ 段。第二次任务从 $6$ 号回撤到 $1$ 号：路径经过 $3$ 号，而 $3$ 号未设补给站，$6$ 到 $1$ 的距离为 $7+3=10$；中途没有可落脚的地点，一段最多行进 $5$，无论如何划分都会有某一段超过 $5$，输出 $-1$。

7 3 4
1 2 3 4 5 6
1 1 1 1 1 1
1 0 1 0 1 0 0
7 1
6 3
7 2

2
1
2

数据范围

对于所有测试数据，保证：

• $1 \le n, q \le 10^5$，$1 \le L \le 10^{14}$；
• $1 \le p_i \le n$ 且 $p_i \ne i$，从任意哨所沿上级链有限步内必能到达 $1$ 号；
• $1 \le w_i \le 10^9$；
• $s_i \in \{0, 1\}$，且 $s_1 = 1$；
• 每次任务保证 $v$ 在 $u$ 的上级链上且 $v \ne u$。

各测试点的约束如下：

• 特殊性质 A：对每个 $i \ge 2$，都有 $p_i = i - 1$。
• 特殊性质 B：对每个 $i$，都有 $s_i = 1$。