Candyland has a candy park, which is not only filled with beautiful scenery and fun attractions but also features many free candy distribution points, attracting many greedy children to visit.

The structure of the candy park is quite unique. It consists of $n$ tourist spots, each with a candy distribution point. We can label the tourist spots from $1$ to $n$. There are $n - 1$ bidirectional roads connecting these spots, and the entire candy park is connected, meaning one can travel from any tourist spot to all other spots in the park using these roads.

The candy park offers a wide variety of candies, with a total of $m$ types, labeled from $1$ to $m$. Each candy distribution point only distributes a specific type of candy, which we denote as $C_i$ for the $i$-th tourist spot.

Visitors to the park do not like to backtrack. They always travel from a specific starting point to a specific destination, visiting the spots along the unique path between them. They can taste one candy of the corresponding type at each tourist spot they pass through.

Everyone has different preferences for different types of candies. Based on visitor feedback, we have obtained the "deliciousness index" of the candies, where the deliciousness index of the $i$-th type of candy is $V_i$. Additionally, if a visitor repeatedly tastes the same type of candy, they will inevitably find it a bit tiresome. Based on quantitative statistics, we have obtained the "novelty index" $W_i$ for the $i$-th time a visitor tastes a certain type of candy. If a visitor tastes the $j$-th type of candy for the $i$-th time, their "joy index" $H$ will increase by the product of the deliciousness index and the novelty index, i.e., $V_j W_i$. The final joy index for a visitor's trip through the park is the sum of these products.

Of course, the type of candy distributed at each point in the park is not necessarily fixed. Sometimes, the type of candy distributed at certain points may change (to one of the $m$ types), with the goal of ensuring visitors always feel surprised.

Little A, a staff member at the candy park, has been assigned the task of calculating the joy index for each visitor's trip based on the park's recent data. However, Little A, who is not good at math, feels dizzy when seeing dense numbers. As Little A's best friend, you decide to help him.

Input

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

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

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

The fourth line to the $(n + 2)$-th line each contain two positive integers $A_i, B_i$, indicating that there is a direct path between these two tourist spots.

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

The next $q$ lines each contain three integers $Type, x, y$, representing an operation:

If $Type$ is $0$, then $1 \leq x \leq n$ and $1 \leq y \leq m$, indicating that the candy type distributed at tourist spot $x$ is changed to $y$.

If $Type$ is $1$, then $1 \leq x, y \leq n$, representing a query for the joy index of a route starting at $x$ and ending at $y$.

Output

For each operation where $Type$ is $1$, output the answer on a new line as a positive integer, following the order of the input.

Examples

Input 1

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

Output 1

84
131
27
84

Constraints

For all data, $1 \leq v_i, w_i \leq 10^6$, $1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq m$, and $w_1, w_2, \dots, w_n$ is a non-increasing sequence, i.e., for any $1 < i \leq n$, $w_i \leq w_{i - 1}$ holds.

Other constraints are shown in the table below: