407660: GYM102864 K Strange Game

shenyunhan is playing a strange game with his best friend. The game is based on a directed graph. Each node in the graph contains an integer which represents the "score" of the node. When playing the game, the two players take turns removing edges from the graph. On each turn, each player can only remove exactly one edge. After some player finishing removing some edge, all nodes that is not reachable from a special node named "origin node" are removed from the graph and the player removing the edge gets a score that is the sum of all scores on these removed nodes. Note that when a node is removed from the graph, all edges associated with the node is also removed.

shenyunhan did not sleep well last night, so he decided to get some help from you. Specifically, shenyunhan will give you a number of questions. In each question, shenyunhan will ask you the score he can get if he removes some edge from the graph in the current turn. Can you help poor shenyunhan?

Node $$$T$$$ is reachable from node $$$S$$$ if and only if one of the following two conditions is true:

• There is an edge from $$$S$$$ to $$$T$$$ present in the graph;
• There is a non-empty sequence of nodes $$$I_1, I_2, I_3, \cdots, I_k$$$ such that $$$S \rightarrow I_1, I_1 \rightarrow I_2, I_2 \rightarrow I_3, \cdots, I_k \rightarrow T$$$ are all present edges in the graph.

The first line contains two space seperated integers $$$N$$$ and $$$M$$$ $$$\left(1 \le N, M \le 4 \times 10^5\right)$$$ representing the number of nodes and the number of edges in the graph. Nodes in the graph are numbered from $$$1$$$ to $$$N$$$ and edges in the graph are numbered from $$$1$$$ to $$$M$$$. Node $$$1$$$ is the "origin node".

Then there are one line containing $$$N$$$ space seperated integers $$$s_i$$$ $$$\left(1 \le i \le N, 1 \le s_i < 2^{31}\right)$$$. The $$$i$$$-th of these integers represents the score of the $$$i$$$-th node.

Then there are $$$M$$$ lines of input, the $$$i$$$-th $$$\left(1 \le i \le M\right)$$$ of which contains two seperated integers $$$u_i$$$ and $$$v_i$$$ $$$\left(1 \le u_i, v_i \le N\right)$$$ representing the $$$i$$$-th edge in the graph that spans from node $$$u_i$$$ to node $$$v_i$$$. It is guaranteed that initially all nodes in the graph are reachable from the "origin node".

Then the input contains a single integer $$$Q$$$ $$$\left(1 \le Q \le 10^5\right)$$$ representing the number of questions shenyunhan asks you.

Then there are $$$Q$$$ lines of input, each of which contains a single integer $$$q_i$$$ $$$\left(1 \le q_i \le M\right)$$$ which is the $$$i$$$-th question asked by shenyunhan. For each question, shenyunhan wants to know how many scores he can get if he removes the $$$q_i$$$-th edge from the graph in the current turn.

For each question asked by shenyunhan, output a single line containing a single integer that represents the answer to the question.

6 7
1 2 3 4 5 6
1 2
1 3
2 3
3 4
3 6
4 5
5 3
7
1
2
3
4
5
6
7

2
0
0
9
6
5
0

The graph given in the example test case is visualized in the following figure.

If shenyunhan removes the 1st edge which spans from node 1 to node 2, then node 2 is unreachable from node 1 so shenyunhan get score 2.

If shenyunhan removes the 2nd edge which spans from node 1 to node 3, no nodes becomes unreachable from node 1 so shenyunhan get a zero score.

Other answers of the given queries are figured out just like above.