FLOOD

Problem

You are given a system of ~N~ water tanks connected by ~M~ pipes. Each tank is numbered with an integer ~i~ where (~1 \le i \le N~) and has a known capacity ~C_i~ - meaning how many units of water it can hold. Each pipe connects two tanks at different heights, and water flows from the higher tank to the lower tank through these pipes (never the other way around).

When a tank overflows, the excess water is directed through the pipes to lower-connected tanks. If multiple pipes connect the tank to lower tanks, the excess water is distributed as follows: the lower tanks are sorted by their numbers in ascending order. The first unit of excess water goes to the first tank in this sorted order, the second unit to the second tank, and so on. If there is more excess water than tanks, this process repeats from the beginning until all excess water is allocated.

However, if a tank overflows and there are no pipes connecting it to a lower tank, the system floods. This scenario must be avoided.

In this problem, you will answer ~Q~ queries about the same system of water tanks. Each query ~j~ (where ~1 \le j \le Q~) will be independent of the others and will have the form:

If all tanks are initially empty, what is the maximum amount of water I can pour into tank ~S_j~ without flooding the system?

Input:

The first line of the input will contain three integers ~N~, ~M~, and ~Q~, separated in pairs by a single space: the number of tanks, the number of pipes, and the number of queries to be answered. The second line will contain ~N~ integers separated in pairs by a single space: the capacities ~C_i~ of the tanks. Each of the next ~M~ lines will contain two integers ~U~ and ~V~, separated by a single space: indicating there is a pipe directed from tank ~U~ (which is at a higher position) to tank ~V~ (which is at a lower position). The last line of the input will contain ~Q~ numbers separated in pairs by a single space: the initial tanks ~S_j~ for the queries to be answered.

Output:

The output should consist of ~Q~ lines, where each line contains exactly one integer: the answer to the corresponding query in order.

Constraints

• ~1 \le N \le 2000~
• ~1 \le M \le 100.000~
• ~1 \le Q \le 2000~
• ~1 \le C_i \le 10^9~
• Each pipe connects two different valid tanks where the first is positioned higher than the second. (In other words, it will be possible for each tank to correspond to a height in such a way that all pipes are consistent.) The same pipe will not be given more than once.
• Time Limit: ~1~ sec.
• Memory Limit: ~128~ MB.

Attention: For large values of ~N~ and ~C_i~, the answer to the queries may exceed ~2^{32}~.

• For test cases with a total value of ~23%~, it will be Q \le 10 and no number in the input file will exceed ~100~.
• For test cases with a total value of ~47%~, each tank will have at most one pipe leading to it.

Example of Input - Output Files:

STDIN (flood.in)

9 10 7
5 3 1 7 9 5 19 2 4
1 2
2 3
3 7
4 5
4 8
1 4
8 9
4 3
4 6
5 7
1 2 3 4 5 6 8

STDOUT (flood.out)

44
23
20
29
28
5
6

Explanation of the example

The system of tanks is shown in the above diagram, where the circles represent the tanks. Inside each circle is the tank number, while outside is written its capacity.

For the first query, if we pour ~44~ units of water into tank ~1~ (the highest one), the following will occur:

• Tank ~1~ receives ~44~ units of water and has a capacity of ~5~ units, so ~39~ units of water will overflow. From these, ~20~ units will go to tank ~2~ and ~19~ units to tank ~4~.
• Tank ~2~ receives ~20~ units of water and has a capacity of ~3~ units, so ~17~ units of water will overflow and go to tank ~3~.
• Tank ~4~ receives ~19~ units of water and has a capacity of ~7~ units, so ~12~ units of water will overflow. These will go to tanks ~3~, ~5~, ~6~, and ~8~, each receiving ~3~ units.
• Tank ~8~ receives ~3~ units of water and has a capacity of ~2~ units, so ~1~ unit of water will overflow and go to tank ~9~.
• Tank ~9~ receives ~1~ unit of water and has a capacity of ~4~ units, so it will not overflow.
• Tank ~3~ receives a total of ~20~ units of water: ~17~ from tank ~2~ and ~3~ from tank ~4~. It has a capacity of ~1~ unit, so ~19~ units will overflow and go to tank ~7~.
• Tank ~7~ receives ~19~ units of water and has a capacity of ~19~ units, so it will not overflow.

Therefore, by pouring ~44~ units of water into tank ~1~, the system does not flood. However, if we add even one more unit of water, tank ~7~ will receive more than ~19~ units of water, causing the system to flood.

Note that if we change the numbering of the tanks in the above system and ask exactly the same questions, the answers may be different due to the way excess water is distributed in case a tank overflows. The second example you will see in Hellenico is the same as the above, but with a different numbering of the tanks.