Candyland has a candy park, which not only has beautiful scenery and fun rides, but also many free candy distribution points, which attracts many greedy children to come to the candy park to play.

The structure of Candy Park is very unique. There are 3 tourist spots, each of which has a candy distribution point. We can number the tourist spots in sequence \(1\) to \(n\) have \(n-1 \) Two-way roads connect these tourist spots, and the entire Candy Park is connected , that is, from any tourist spot, you can reach all other tourist spots in the park through these roads.

The variety of candies distributed in the Candy Park is very rich, with a total of \(m\) Species, their numbers are \(1\) to \(m\)

Each candy distribution station only distributes a certain type of candy. We use \(c_i\) To represent \(i\) Candy at the \(i-th\) tour point.

Visitors who come to the park don't like to go back and forth . They always start from a specific tourist spot and go to another specific tourist spot, and visit the attractions along the way. This route must be unique. When they pass each tourist spot, they can taste a candy of the corresponding type.

People have different preferences for different types of candies. Based on the feedback and scores from tourists, we got the deliciousness index of the candies.

\(i\) The deliciousness index of the candy is \(v_i\)

In addition, if a tourist repeatedly tastes the same kind of candy, he will definitely feel a little tired of it. Based on quantitative statistics, we have obtained the tourists' \(i\) Novelty index of tasting a certain type of candy \(w_i\) If a tourist \(i\) Tasting \(j\) kind of candy, then his pleasure index \(H\) The product of the corresponding deliciousness index and novelty index will be increased, that is, \(v_j w_i\) The visitor's enjoyment of the park will ultimately be the sum of these products.

Of course, the types of candy distributed at each candy distribution point in the park are not necessarily fixed. Sometimes, the types of candy distributed at some candy points may change (it will only be \(m\) The purpose is to always surprise visitors.

Xiao A, a staff member of Candy Park, received a task, which is to calculate the pleasure index of each visitor in the park based on the park's recent data. However, Xiao A, who is not good at math, feels dizzy when he sees the dense numbers. As Xiao A's best friend, you decide to help him.

Формат вхідних даних

The first line contains three positive integers \(n, m, q\), representing the number of visiting spots, the number of candy types and the number of operations respectively.

The second line contains \(m\) positive integer \(v_1, v_2, \dots, v_m\).

The third line contains \(n\) positive integer \(w_1, w_2, \dots, w_n\).

The fourth to the \(n + 2\) Lines, each containing two positive integers \(a_i, b_i\), indicating that there is a path that can directly reach these two tourist points.

No. \(n + 3\) Line contains \(n\) positive integer \(c_1, c_2, \dots, c_n\).

Next \(q\) Lines, each containing three integers \(t, x, y\), indicating an operation:

like \(t=0\) \(1 \leq x \leq n\), \(1 \leq y \leq m\), indicating that the number is \(x\)The type of candy distributed at the tourist spot is changed to \(y\);

like \(t=1\) \(1 \leq x, y \leq n\), indicating that the starting point is \(x\), the end point is \(y\) The route inquiry pleasure index.

Формат вихідних даних

In the order of input, for each \(t=1\) The operation outputs a line with a positive integer representing the answer.

Формат вхідних даних

The first line contains three positive integers \(n, m, q\), representing the number of visiting spots, the number of candy types and the number of operations respectively.

The second line contains \(m\)positive integer \(v_1, v_2, \dots, v_m\).

The third line contains \(n\)positive integer \(w_1, w_2, \dots, w_n\).

The fourth to the \(n + 2\)Lines, each containing two positive integers \(a_i, b_i\), indicating that there is a path that can directly reach these two tourist points.

No. \(n + 3\)Line contains \(n\)positive integer \(c_1, c_2, \dots, c_n\).

Next Steps \(q\)Lines, each containing three integers \(t, x, y\), indicating an operation:

like \(t\)for \(0\),but \(1 \leq x \leq n\), \(1 \leq y \leq m\), indicating that the number is \(x\)The type of candy distributed at the tourist spot is changed to \(y\);

like \(t\)for \(1\),but \(1 \leq x, y \leq n\), indicating that the starting point is \(x\), the end point is \(y\)The route inquiry pleasure index.

Формат вихідних даних

In the order of input, for each \(t\)for \(1\)The operation outputs a line with a 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