Candyland 有一座糖果公園，公園裡不僅有美麗的風景、好玩的遊樂項目，還有許多免費糖果的發放點，這引來了許多貪吃的小朋友來糖果公園玩。

糖果公園的結構十分奇特，它由 $n$ 個遊覽點構成，每個遊覽點都有一個糖果發放處，我們可以依次將遊覽點編號為 $1$ 至 $n$。有 $n - 1$ 條雙向道路連接著這些遊覽點，並且整個糖果公園都是連通的，即從任何一個遊覽點出發都可以通過這些道路到達公園裡的所有其它遊覽點。

糖果公園所發放的糖果種類非常豐富，總共有 $m$ 種，它們的編號依次為 $1$ 至 $m$。每一個糖果發放處都只發放某種特定的糖果，我們用 $C_i$ 來表示 $i$ 號遊覽點的糖果。

來到公園裡遊玩的遊客都不喜歡走回頭路，他們總是從某個特定的遊覽點出發前往另一個特定的遊覽點，並遊覽途中的景點，這條路線一定是唯一的。他們經過每個遊覽點，都可以品嚐到一顆對應種類的糖果。

大家對不同類型的糖果的喜愛程度都不盡相同。根據遊客們的反饋打分，我們得到了糖果的美味指數，第 $i$ 種糖果的美味指數為 $V_i$。另外，如果一位遊客反覆地品嚐同一種類的糖果，他肯定會覺得有一些膩。根據量化統計，我們得到了遊客第 $i$ 次品嚐某類糖果的新奇指數 $W_i$，如果一位遊客第 $i$ 次品嚐第 $j$ 種糖果，那麼他的愉悅指數 $H$ 將會增加對應的美味指數與新奇指數的乘積，即 $V_j W_i$。這位遊客遊覽公園的愉悅指數最終將是這些乘積的和。

當然，公園中每個糖果發放點所發放的糖果種類不一定是一成不變的。有時，一些糖果點所發放的糖果種類可能會更改（也只會是 $m$ 種中的一種），這樣的目的是能夠讓遊客們總是感受到驚喜。

糖果公園的工作人員小 A 接到了一個任務，那就是根據公園最近的數據統計出每位遊客遊玩公園的愉悅指數。但數學不好的小 A 一看到密密麻麻的數字就覺得頭暈，作為小 A 最好的朋友，你決定幫他一把。

輸入格式

第一行包含三個正整數 $n, m, q$，分別表示遊覽點個數、糖果種類數和操作次數。

第二行包含 $m$ 個正整數 $V_1, V_2, \cdots, V_m$。

第三行包含 $n$ 個正整數 $W_1, W_2, \cdots, W_n$。

第四行到第 $n + 2$ 行，每行包含兩個正整數 $A_i, B_i$，表示這兩個遊覽點之間有路徑可以直接到達。

第 $n + 3$ 行包含 $n$ 個正整數 $C_1, C_2, \dots, C_n$。

接下來 $q$ 行，每行包含三個整數 $Type, x, y$，表示一次操作：

若 $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

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}$。

其他的限制條件如下表所示：