题目描述

As the competition was nearing its end, a banquet was held. For decoration, there was a tree with $n$ light bulbs numbered from $1$ to $n$ on it, where the $i$-th bulb has a $\textit{beauty}$ of $w_i$. The bulbs are connected by $n - 1$ circuits. Specifically, for each $i$ from $2$ to $n$, there is a circuit connecting the $i$-th bulb and the $f_i$-th bulb ($1 \leq f_i < i$).

There is a row of $m$ switches that control the bulbs' lighting. Pressing the $i$-th switch toggles the state of all bulbs on the simple path from bulb $1$ to bulb $o_i$ on the tree (i.e., bulbs that are on turn off, and those that are off turn on).

$q$ children will interact with the tree. The process for the $i$-th child is described by three integers $l_i$, $r_i$, and $x_i$:

• Initially, all bulbs are off.
• Then, the switches from the $l_i$-th to the $r_i$-th are pressed in sequence.
• Finally, a photo is taken of the bulbs on the simple path from $1$ to $x_i$.

The $\textit{total beauty}$ of a photo is the sum of the $\textit{beauty}$ of all bulbs that are on in the photo. Your task is to compute this value for each of the $q$ children.

输入格式

The first line of the input contains three integers $n$, $m$, and $q$ ($1 \leq n, m, q \leq 5 \cdot 10^5$), where $n$ is the number of bulbs, $m$ is the number of switches, and $q$ is the number of children.

The second line of the input contains $n-1$ integers $f_2, f_3, \ldots, f_n$ ($1 \leq f_i < i$), where $f_i$ represents a circuit between the $i$-th bulb and the $f_i$-th bulb.

The third line of the input contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \leq w_i \leq 1000$), where $w_i$ is the \textit{beauty} of the $i$-th bulb.

The next $m$ lines of the input describe the switches. The $i$-th line of these contains a single integer $o_i$ ($1 \leq o_i \leq n$).

The next $q$ lines of the input describe the interaction process of the children. The $i$-th line of these contains three integers $l_i$, $r_i$, and $x_i$ ($1\le l_i\le r_i\le m$, $1\le x_i\le n$).

输出格式

Output $q$ lines, each containing an integer, representing the $\textit{total beauty}$ of each photo.

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

提示

For the first child:

• First, he pressed the first switch, causing the first and the second bulbs to turn on.
• Then, he pressed the second switch, causing the first and the second bulbs to turn off while the third bulb turns on.
• He took a photo of bulbs $1, 2, 3$, and $5$. In the photo, only the 3rd bulb was lit, resulting in a beauty of $48$.