Candylandにはキャンディ公園があります。この公園には美しい景色や楽しいアトラクションだけでなく、多くの無料キャンディ配布所があり、多くの食いしん坊な子供たちがキャンディ公園に遊びに来ます。

キャンディ公園の構造は非常に独特で、$n$ 個の観光スポットで構成されており、各観光スポットにはキャンディ配布所があります。観光スポットには $1$ から $n$ までの番号が付けられています。$n - 1$ 本の双方向道路がこれらの観光スポットを繋いでおり、公園全体は連結しています。つまり、どの観光スポットから出発しても、これらの道路を通って公園内の他のすべての観光スポットに到達することができます。

キャンディ公園で配布されるキャンディの種類は非常に豊富で、合計 $m$ 種類あり、それぞれ $1$ から $m$ までの番号が付けられています。各キャンディ配布所では特定の種類のキャンディのみが配布されており、$i$ 番の観光スポットで配布されるキャンディの種類を $C_i$ と表します。

公園に遊びに来る観光客は引き返すことを好まないため、ある特定の観光スポットから別の特定の観光スポットへ向かい、その途中のスポットを観光します。このルートは必ず一意に定まります。彼らは通過する各観光スポットで、その場所に対応する種類のキャンディを1つ味わうことができます。

人々が異なる種類のキャンディに対して抱く好みの度合いはそれぞれ異なります。観光客からのフィードバックに基づき、キャンディの美味しさ指数が得られており、第 $i$ 種類のキャンディの美味しさ指数は $V_i$ です。また、観光客が同じ種類のキャンディを繰り返し味わうと、飽きてしまうことがあります。統計に基づき、観光客が第 $i$ 回目に特定の種類のキャンディを味わう際の新鮮さ指数 $W_i$ が得られています。もし観光客が第 $i$ 回目に第 $j$ 種類のキャンディを味わった場合、その愉悦指数 $H$ は、美味しさ指数と新鮮さ指数の積、すなわち $V_j W_i$ だけ増加します。観光客が公園を観光した際の最終的な愉悦指数は、これらの積の合計となります。

もちろん、公園内の各キャンディ配布所で配布されるキャンディの種類は固定されているわけではありません。観光客が常に驚きを感じられるように、一部の配布所で配布されるキャンディの種類が変更されることがあります（変更先も $m$ 種類のうちのいずれかです）。

キャンディ公園のスタッフである小Aは、「公園の最近のデータに基づいて、各観光客の公園観光における愉悦指数を算出する」という任務を受けました。しかし、数学が苦手な小Aは、数字の羅列を見ると頭が痛くなってしまいます。小Aの親友であるあなたは、彼を助けることにしました。

入力

1行目には、3つの正整数 $n, m, q$ が含まれており、それぞれ観光スポットの数、キャンディの種類の数、操作の回数を表します。

2行目には、$m$ 個の正整数 $V_1, V_2, \cdots, V_m$ が含まれています。

3行目には、$n$ 個の正整数 $W_1, W_2, \cdots, W_n$ が含まれています。

4行目から $n + 2$ 行目まで、各行には2つの正整数 $A_i, B_i$ が含まれており、これら2つの観光スポット間に直接到達可能な経路があることを示します。

$n + 3$ 行目には、$n$ 個の正整数 $C_1, C_2, \dots, C_n$ が含まれています。

続く $q$ 行には、各行に3つの整数 $Type, x, y$ が含まれており、1回の操作を表します。

$Type$ が $0$ の場合、$1 \leq x \leq n$、$1 \leq y \leq m$ であり、番号 $x$ の観光スポットで配布されるキャンディの種類が $y$ に変更されることを意味します。

$Type$ が $1$ の場合、$1 \leq x, y \leq n$ であり、出発点が $x$、終点が $y$ であるルートの愉悦指数を問い合わせることを意味します。

出力

入力された順序に従い、$Type$ が $1$ である各操作に対して、答えを1行ずつ正整数で出力してください。

入出力例

入出力例 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

出力例 1

84
131
27
84

制約

すべてのデータにおいて、$1 \leq v_i, w_i \leq 10^6$、$1 \leq a_i, b_i \leq n$、$1 \leq c_i \leq m$ であり、$w_1, w_2, \dots, w_n$ は非増加数列です。つまり、任意の $1 < i \leq n$ に対して $w_i \leq w_{i - 1}$ が成り立ちます。

その他の制限条件は以下の表の通りです。