Description

Candyland has a Candy Park. Besides beautiful scenery and fun rides, there are many free candy distribution points, which attracts many candy-loving children to visit.

The structure of the Candy Park is peculiar. It consists of $n$ sightseeing spots, and each spot has a candy station. We number the spots from $1$ to $n$. There are $n - 1$ bidirectional roads connecting these spots, and the entire park is connected, meaning that starting from any spot, one can reach all other spots in the park via these roads.

There are $m$ types of candies in total, numbered from $1$ to $m$. Each candy station only distributes a specific type of candy. We use $C_i$ to denote the candy type at spot $i$.

Visitors do not like to retrace their steps. They always travel from a particular starting spot to a particular ending spot, visiting the spots along the way. This route is unique. When they pass each spot, they can taste one candy of the corresponding type.

People have different preferences for different types of candies. Based on visitor ratings, we obtained the tastiness index of candies: the tastiness index of the $i$-th type of candy is $V_i$. In addition, if a visitor repeatedly tastes the same type of candy, they will feel a bit bored. According to quantitative statistics, the novelty index for the $i$-th time tasting a certain type of candy is $W_i$. If a visitor tastes the $j$-th type of candy for the $i$-th time, their happiness index $H$ increases by the product of the corresponding tastiness index and novelty index, i.e., $V_j \times W_i$. The visitor’s final happiness index is the sum of these products.

Of course, the candy type distributed at each station may change from time to time (but always to one of the $m$ types), so that visitors can always feel surprised.

Staff member A received a task to compute each visitor’s happiness index based on recent park data. But A is not good at math and feels dizzy when seeing rows of numbers. As A’s best friend, you decide to help.

Input Format

The first line contains three positive integers $n, m, q$, representing the number of spots, the number of candy types, and the number of operations.

The second line contains $m$ positive integers $V_1, V_2, \ldots, V_m$.

The third line contains $n$ positive integers $W_1, W_2, \ldots, W_n$.

From the 4th line to the $(n + 2)$-th line, each line contains two positive integers $A_i, B_i$, indicating that there is a road directly connecting these two spots.

The $(n + 3)$-th line contains $n$ positive integers $C_1, C_2, \ldots, C_n$.

Then there are $q$ lines. Each line contains three integers $Type, x, y$, representing an operation:

• If $Type$ is $0$, then $1 \le x \le n$, $1 \le y \le m$, meaning that the candy type at spot $x$ is changed to $y$.
• If $Type$ is $1$, then $1 \le x, y \le n$, meaning a query for the happiness index along the path from $x$ to $y$.

Output Format

In the order of the input, for each operation with $Type = 1$, output one line with a single positive integer representing the answer.

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

84
131
27
84

Hint

[Sample explanation]

We use

to denote nodes with $C_i$ equal to $1$, $2$, $3$. Before modification:

After changing $C_2$ to $1$:

[Constraints]

For all testdata: $1 \le V_i, W_i \le 10^6$, $1 \le A_i, B_i \le n$, $1 \le C_i \le m$, and $W_1, W_2, \ldots, W_n$ is a non-increasing sequence, i.e., for any $1 < i \le n$, it holds that $W_i \le W_{i-1}$.

Other constraint conditions are as shown in the table below:

Translated by ChatGPT 5