As the competition was nearing its end, a banquet was held. For decoration, there was a tree with light bulbs numbered from to on it, where the -th bulb has a of . The bulbs are connected by circuits. Specifically, for each from to , there is a circuit connecting the -th bulb and the -th bulb ().
There is a row of switches that control the bulbs' lighting. Pressing the -th switch toggles the state of all bulbs on the simple path from bulb to bulb on the tree (i.e., bulbs that are on turn off, and those that are off turn on).
children will interact with the tree. The process for the -th child is described by three integers , , and :
Initially, all bulbs are off.
Then, the switches from the -th to the -th are pressed in sequence.
Finally, a photo is taken of the bulbs on the simple path from to .
The of a photo is the sum of the of all bulbs that are on in the photo. Your task is to compute this value for each of the children.
输入格式
The first line of the input contains three integers , , and (), where is the number of bulbs, is the number of switches, and is the number of children.
The second line of the input contains integers (), where represents a circuit between the -th bulb and the -th bulb.
The third line of the input contains integers (), where is the \textit{beauty} of the -th bulb.
The next lines of the input describe the switches. The -th line of these contains a single integer ().
The next lines of the input describe the interaction process of the children. The -th line of these contains three integers , , and (, ).
输出格式
Output lines, each containing an integer, representing the of each photo.
