Description

随着比赛接近尾声，举行了一场宴会。作为装饰，树上挂着 $n$ 个编号为 $1$ 到 $n$ 的灯泡，第 $i$ 个灯泡具有一个 美丽值 $w_i$。这些灯泡通过 $n-1$ 条电路连接。具体而言，对于每个 $i$（$2 \leq i \leq n$），存在一条电路连接第 $i$ 个灯泡和第 $f_i$ 个灯泡（$1 \leq f_i < i$）。

有一排 $m$ 个开关控制这些灯泡的亮灭。按下第 $i$ 个开关，会切换从灯泡 $1$ 到灯泡 $o_i$ 这条简单路径上的所有灯泡的状态（即原本亮的灯泡会熄灭，原本灭的灯泡会点亮）。

接下来有 $q$ 个小朋友会与这棵树进行互动。第 $i$ 个小朋友的操作由三个整数 $l_i$、$r_i$ 和 $x_i$ 描述：

• 起初，所有灯泡都是熄灭的；
• 接着，依次按下第 $l_i$ 个到第 $r_i$ 个开关；
• 最后，拍摄从灯泡 $1$ 到灯泡 $x_i$ 这条路径上所有灯泡的照片。

一张照片的 总美丽值 定义为照片中所有亮着的灯泡的 美丽值 之和。你的任务是计算每个小朋友拍摄的照片的总美丽值。

Input Format

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m, q \leq 5 \cdot 10^5$），分别表示灯泡的数量、开关的数量以及小朋友的数量。

第二行包含 $n-1$ 个整数 $f_2, f_3, \ldots, f_n$（$1 \leq f_i < i$），其中 $f_i$ 表示存在一条电路连接第 $i$ 个灯泡和第 $f_i$ 个灯泡。

第三行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$0 \leq w_i \leq 1000$），其中 $w_i$ 表示第 $i$ 个灯泡的 美丽值。

接下来的 $m$ 行描述这些开关。第 $i$ 行包含一个整数 $o_i$（$1 \leq o_i \leq n$），表示第 $i$ 个开关控制的路径终点灯泡编号。

之后的 $q$ 行描述每个小朋友的互动过程。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 \leq l_i \leq r_i \leq m$，$1 \leq x_i \leq n$）。

Output Format

输出共 $q$ 行，每行包含一个整数，表示对应照片的 总美丽值。

5 3 7
1 2 3 3
907 609 48 670 184
2
3
5
1 2 5
1 3 3
1 3 2
2 3 1
2 3 3
2 3 4
3 3 5

48
1516
1516
0
0
0
1748

Hint

对于第一个小朋友：

• 首先，他按下第一个开关，使得第 1 个和第 2 个灯泡被点亮；
• 接着，他按下第二个开关，使第 1 个和第 2 个灯泡熄灭，而第 3 个灯泡点亮；
• 最后，他拍摄了从灯泡 $1$ 到灯泡 $5$ 的路径，也就是灯泡 $1, 2, 3, 5$。在照片中，只有第 3 个灯泡是亮的，因此总美丽值为 $48$。

翻译由 ChatGPT-5 完成