W Candyland znajduje się park cukierków, który słynie nie tylko z pięknych krajobrazów i atrakcji, ale także z wielu punktów rozdających darmowe słodycze, co przyciąga mnóstwo łakomczuchów.

Struktura parku jest bardzo osobliwa: składa się on z $n$ punktów widokowych, z których każdy posiada punkt wydawania cukierków. Punkty te są ponumerowane od $1$ do $n$. Istnieje $n - 1$ dwukierunkowych dróg łączących te punkty, a cały park jest spójny, co oznacza, że z każdego punktu można dotrzeć do wszystkich pozostałych.

W parku dostępnych jest $m$ rodzajów cukierków, ponumerowanych od $1$ do $m$. Każdy punkt wydawania cukierków oferuje tylko jeden konkretny rodzaj, który oznaczamy jako $C_i$ dla punktu $i$.

Odwiedzający park nie lubią wracać tą samą drogą. Zawsze wyruszają z określonego punktu do innego, poruszając się po jedynej dostępnej ścieżce między nimi. Przechodząc przez każdy punkt widokowy, mogą skosztować jednego cukierka danego rodzaju.

Poziom zadowolenia z różnych rodzajów cukierków jest różny. Na podstawie opinii odwiedzających określono indeks smakowitości $V_i$ dla każdego rodzaju cukierka $i$. Ponadto, jeśli odwiedzający wielokrotnie kosztuje tego samego rodzaju cukierka, zaczyna odczuwać znużenie. Na podstawie statystyk określono indeks nowości $W_i$ dla $i$-tej degustacji danego rodzaju cukierka. Jeśli odwiedzający kosztuje $j$-ty rodzaj cukierka po raz $i$-ty, jego wskaźnik przyjemności $H$ wzrasta o iloczyn indeksu smakowitości i indeksu nowości, czyli $V_j W_i$. Całkowity wskaźnik przyjemności z wycieczki po parku jest sumą tych iloczynów.

Oczywiście, rodzaje cukierków wydawane w poszczególnych punktach nie muszą być stałe. Czasami rodzaj cukierka w danym punkcie może ulec zmianie (na jeden z $m$ dostępnych rodzajów), aby odwiedzający zawsze mogli liczyć na niespodzianki.

Pracownik parku, mały A, otrzymał zadanie obliczenia wskaźnika przyjemności każdego odwiedzającego na podstawie ostatnich danych statystycznych. Jednak mały A, który nie przepada za matematyką, czuje zawroty głowy na widok gęstych kolumn liczb. Jako jego najlepszy przyjaciel, postanawiasz mu pomóc.

Wejście

Pierwsza linia zawiera trzy dodatnie liczby całkowite $n, m, q$, oznaczające odpowiednio liczbę punktów widokowych, liczbę rodzajów cukierków oraz liczbę operacji.

Druga linia zawiera $m$ dodatnich liczb całkowitych $V_1, V_2, \cdots, V_m$.

Trzecia linia zawiera $n$ dodatnich liczb całkowitych $W_1, W_2, \cdots, W_n$.

Kolejne $n - 1$ linii zawiera po dwie dodatnie liczby całkowite $A_i, B_i$, oznaczające bezpośrednie połączenie między tymi punktami.

Linia $n + 3$ zawiera $n$ dodatnich liczb całkowitych $C_1, C_2, \dots, C_n$.

Następnie $q$ linii zawiera po trzy liczby całkowite $Type, x, y$, opisujące operację:

Jeśli $Type$ wynosi $0$, to $1 \leq x \leq n$ oraz $1 \leq y \leq m$, co oznacza, że rodzaj cukierka w punkcie $x$ zostaje zmieniony na $y$.

Jeśli $Type$ wynosi $1$, to $1 \leq x, y \leq n$, co oznacza zapytanie o wskaźnik przyjemności dla trasy z punktu $x$ do punktu $y$.

Wyjście

Dla każdego zapytania typu $1$, wypisz w osobnej linii wynik w postaci liczby całkowitej, zgodnie z kolejnością operacji w wejściu.

Przykład

Wejście 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

Wyjście 1

84
131
27
84

Ograniczenia

Dla wszystkich danych wejściowych: $1 \leq v_i, w_i \leq 10^6$, $1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq m$. Ciąg $w_1, w_2, \dots, w_n$ jest nierosnący, tzn. dla każdego $1 < i \leq n$ zachodzi $w_i \leq w_{i - 1}$.

Pozostałe ograniczenia przedstawiono w poniższej tabeli: