In a market of mangoes, there are N sellers numbered from 1 to N. The i-th seller initially charges a price of A_{i} coins for each of their mangoes. However, the sellers are very competitive, and they will change prices based on other sellers nearby.

You have a simple graph (unweighted, undirected graph containing no self-loops or multiple edges) G with N vertices and M edges. There is an edge between two sellers if and only if they are neighbours. When you buy a mango from a seller numbered X, the following occurs:

Seller X keeps his price the same.
Every seller Y who is a neighbour of X increases their price by 1, that is, A_{Y} = A_{Y} + 1 for every Y who is a neighbour of X.
Every other seller Z who is not a neighbour of X decreases their price by 1; that is, A_{Z} = A_{Z} - 1 for every Z who is not a neighbour of X.

Prices can become zero or negative during this process.

Now you should process Q queries of the following three types:
$\texttt{+} u v$ — Add an edge between nodes u and v in the graph. It's guaranteed there is no edge between u and v currently.
$\texttt{-} u v$ — Remove an edge between nodes u and v in the graph. It's guaranteed there is an edge between u and v currently.
$\texttt{$?} — Find the minimum amount of money you need to pay so that you can buy exactly one mango from every seller. After queries of this type, the prices of all sellers are reset to their initial value.

------ Input Format ------

• The first line contains two integers N and M - the number of sellers and the number of edges in the graph.
• The second line contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the price array A.
• The next M lines each contain two integers u and v (1 ≤ u,v ≤ $N, u \ne v),$ representing an edge of G.
• The next line contains the integer Q — the number of queries.
• The next Q lines contain the queries. Each query is in the format given in the problem statement.
• There is at least one query of type $\texttt{$?}.

------ Output Format ------

For each query of type $\texttt{$?}, output one integer — the minimum amount of money you need to pay so that you can buy exactly one mango from each seller.

------ Constraints ------

$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ M ≤ \min(\binom{N}{2}, 10^{5})$
$1 ≤ A_{i} ≤ 10^{9}$
- It's guaranteed that $G$ is a simple graph, that is, it is an unweighted, undirected graph containing no self-loops or multiple edges.

----- Sample Input 1 ------
4 3
8 9 6 10
2 1
1 3
3 4
6
?
+ 2 3
+ 4 2
- 3 1
+ 1 4
?

----- Sample Output 1 ------
33
37

----- explanation 1 ------
In the sample test, the first query of type $\texttt{?}$ is pictured below. The $i$-th node (from left to right) contains the price of the $i$-th seller. If we buy mangoes from the sellers $1$, $4$, $3$, $2$, in that order, then we can pay $8$, $9$, $8$, and $8$ coins for the mangoes, respectively, paying a total $33$ coins. It can be proven that this is indeed the minimum amount possible.

It can be proven that for the second query of type $\texttt{?}$, the minimum amount we can pay is $37$ coins. Note that the prices of the mangoes reset after each query of type $\texttt{?}$.

见题面

见题面