G. Graph Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Forgotten Caverns form a network of $$$n$$$ chambers, connected by $$$m$$$ bidirectional tunnels. This network is a connected, undirected, unweighted graph with vertices numbered from $$$1$$$ to $$$n$$$.

Each chamber $$$i$$$ has a difficulty value $$$a_i$$$. Some chambers also contain ancient treasures, indicated by $$$b_i \in \{0,1\}$$$: if $$$b_i=1$$$, there is a treasure in chamber $$$i$$$; if $$$b_i=0$$$, there is none.

You are an adventurer exploring these caverns. You begin in some chamber with magical power $$$p$$$. From your current chamber $$$u$$$, you may move to any adjacent chamber $$$v$$$ through a tunnel:

  • If $$$a_v \gt p$$$, you must pay $$$(a_v - p)^2$$$ coins and set $$$p \leftarrow a_v$$$. Otherwise, you pay nothing and $$$p$$$ stays the same.
  • In both cases, you move to $$$v$$$ (so $$$u \leftarrow v$$$).

You may visit the same chamber any number of times, and you may use the same tunnel any number of times.

You are asked to process $$$q$$$ queries of the following two types:

  • 1 u p — Starting at chamber $$$u$$$ with initial power $$$p$$$ (guaranteed $$$p \ge a_u$$$), compute the minimum number of coins required to visit all chambers that currently contain treasures at least once. If there are no treasures, the answer is $$$0$$$.
  • 2 l r — For all $$$i$$$ with $$$l \le i \le r$$$, toggle whether chamber $$$i$$$ contains a treasure: if a treasure exists, remove it; otherwise, place one.

The treasure configuration is persistent and updates after each type-2 query.

Input

The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$n-1 \le m \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of chambers, tunnels, and queries respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the difficulty of each chamber.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$b_i \in \{0,1\}$$$) — the initial treasure configuration.

The next $$$m$$$ lines each contain two integers $$$x, y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — a tunnel between chambers $$$x$$$ and $$$y$$$.

The next $$$q$$$ lines each describe one query:

  • For a query of type-1, the line has the form 1 u p, where $$$1 \le u \le n$$$ and $$$a_u \le p \le 10^9$$$.
  • For a query of type-2, the line has the form 2 l r, where $$$1 \le l \le r \le n$$$.

It is guaranteed that the graph is connected, with no multiple edges and no self-loops.

It is guaranteed that there will be at least one type-1 query.

Output

For each query of type-1, output a single integer — the minimum number of coins required.

Example
Input
5 7 8
6 12 10 15 5
1 0 1 0 0
2 3
4 5
1 3
3 4
4 1
5 3
2 5
1 1 6
1 4 15
2 3 4
1 1 6
1 1 9
2 2 4
1 2 20
1 3 10
Output
16
0
29
14
0
4
Note

In the first example, the difficulties are $$$a = [6,12,10,15,5]$$$ and the initial treasures are at chambers $$$\{1,3\}$$$.

  • Query 1 (1 1 6): Path: $$$1 \to 3$$$. Cost: $$$(10-6)^2 = 16$$$.
  • Query 2 (1 4 15): Path: $$$4 \to 5 \to 3 \to 1$$$. Costs: $$$0+0+0=0$$$.
  • Query 3 (2 3 4): Toggle treasures in $$$[3,4]$$$. Now treasures are at chambers $$$\{1,4\}$$$.
  • Query 4 (1 1 6): Path: $$$1 \to 3 \to 2 \to 5 \to 4$$$. Costs: $$$(10-6)^2 + (12-10)^2 + (15-12)^2 = 29$$$.
  • Query 5 (1 1 9): Path: $$$1 \to 3 \to 2 \to 5 \to 4$$$. Costs: $$$(10-9)^2 + (12-10)^2 + (15-12)^2 = 14$$$
  • Query 6 (2 2 4): Toggle treasures in $$$[2,4]$$$. Now treasures are at chambers $$$\{1,2,3\}$$$.
  • Query 7 (1 2 20): Treasures $$$\{1,2,3\}$$$. Path: $$$2 \to 5 \to 4 \to 1 \to 3$$$. Costs: $$$0+0+0+0=0$$$.
  • Query 8 (1 3 10): Treasures $$$\{1,2,3\}$$$. Path: $$$3 \to 2 \to 3 \to 1$$$. Costs: $$$0 + (12-10)^2 + 0=4$$$.