In a distant country, there are $n$ cities labeled with numbers from $1$ to $n$. Airline routes—daily flights in both directions—are established between $m$ pairs of distinct cities. Some cities are hubs, and certain airlines dedicate more attention and resources to them. Finally, each city has a certain number of potential passengers, and as time passes, this number may vary.

Figure 1: Illustration of the first test data example: the current influence of city 3 is 22, and of city 6 is 8.

For a given hub city $a$, its influence is the total number of potential passengers who are either located in city $a$ or can reach city $a$ through a sequence of flights without passing through any other hub city (and without starting from any other hub city). An airline network is given in which hub cities are marked, along with the initial number of potential passengers in each city. Additionally, $q$ events are given, where each event is one of the following:

• “1 $a$ $p_a$” — the number of potential passengers in city $a$ changes and is now $p_a$.
• “2 $a$” — we are interested in the current influence of hub city $a$.

Find the answers to all events of the second type.

Input

The first line contains natural numbers $n$ and $m$ — the number of cities and the number of routes. The next line contains a sequence of $n$ integers $k_1, k_2, \dots, k_n$ — the number $k_j$ is $1$ if city $j$ is a hub, and $0$ otherwise. The next line contains a sequence of $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_j \le 10^9$) — $p_j$ is the initial number of potential passengers in city $j$. In the $j$-th of the following $m$ lines, there are two distinct natural numbers $a_j$ and $b_j$ ($1 \le a_j, b_j \le n$) — the labels of cities directly connected by a route. It is not necessary for the cities and routes to form a connected graph.

The next line contains a natural number $q$ — the number of events. In the $j$-th of the following $q$ lines, there is the $j$-th event. Each event is either of the form “1 $a$ $p_a$” where $a$ is the city label ($1 \le a \le n$) and $p_a$ is the new number of potential passengers ($0 \le p_a \le 10^9$), or of the form “2 $a$” where $a$ is the label of a city that is a hub. At least one event will be of type 2.

Output

Print as many lines as there are events of type 2 in the input. In the $j$-th line, print the requested influence of the hub city from the $j$-th event of type 2 in the input.

Subtasks

Examples

Input 1

6 7
0 0 1 0 0 1
4 3 0 9 6 2
1 2
2 3
4 3
4 1
5 3
5 6
3 6
2
2 3
2 6

Output 1

22
8

Input 2

6 6
1 0 1 1 0 0
1 2 4 3 5 6
1 2
1 3
3 2
6 5
4 5
1 6
8
2 3
1 2 7
2 3
2 1
1 6 0
1 4 9
2 1
2 4

Output 2

6
11
19
13
14