Mango Market
In a market of mangoes, there are
sellers numbered from to . The -th seller initially charges a price of 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) with vertices and edges. There is an edge between two sellers if and only if they are neighbours. When you buy a mango from a seller numbered , the following occurs:
- Seller keeps his price the same.
- Every seller who is a neighbour of increases their price by , that is, for every who is a neighbour of .
- Every other seller who is not a neighbour of decreases their price by ; that is, for every who is not a neighbour of .
Prices can become zero or negative during this process.
Now you should process queries of the following three types:
- — Add an edge between nodes and in the graph. It's guaranteed there is no edge between and currently.
- — Remove an edge between nodes and in the graph. It's guaranteed there is an edge between and currently.
- — 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 and - the number of sellers and the number of edges in the graph.
- The second line contains space-separated integers denoting the price array .
- The next lines each contain two integers and (, ), representing an edge of .
- The next line contains the integer — the number of queries.
- The next lines contain the queries. Each query is in the format given in the problem statement.
- There is at least one query of type .
Output Format
For each query of type , output one integer — the minimum amount of money you need to pay so that you can buy exactly one mango from each seller.
Constraints
- It's guaranteed that 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
In the sample test, the first query of type is pictured below. The -th node (from left to right) contains the price of the -th seller. If we buy mangoes from the sellers , , , , in that order, then we can pay , , , and coins for the mangoes, respectively, paying a total coins. It can be proven that this is indeed the minimum amount possible.
It can be proven that for the second query of type , the minimum amount we can pay is coins. Note that the prices of the mangoes reset after each query of type .
Comments
Post a Comment