Woburn Challenge 2015-16 Round 4 - Senior Division

MI6 has received intelligence that members of the evil Spectre organization may be holding a gathering somewhere along a certain street in London. Unfortunately, they're not sure exactly in which building this gathering will take place. As such, they'll need to recruit some agents to stake out the street and look for suspicious activity.

The street can be represented by a number line. There are ~N~ ~(1 \le N \le 300\,000)~ suspicious buildings which must be monitored, with the ~i~-th one at position ~B_i~ ~(-10^9 \le B_i \le 10^9)~. There are also ~M~ ~(1 \le M \le 300\,000)~ agents stationed along the street, with the ~i~-th one at position ~A_i~ ~(-10^9 \le A_i \le 10^9)~. All ~N + M~ of these positions are distinct. Agent ~i~ has a sight range of ~R_i~ ~(1 \le R_i \le 10^9)~, meaning that they're able to keep watch over all buildings at positions in the inclusive range of positions ~[A_i - R_i, A_i + R_i]~. Times are tough at MI6, with the agents not even willing to take this assignment for free – M will have to pay agent ~i~ a fee of ~2^i~ dollars to stay at their post, otherwise they'll get bored of the stakeout and go out for some steak instead.

In light of this monetary issue, M will need to decide on a tradeoff between cost and thoroughness. A hired agent can successfully keep an eye on all buildings in his range simultaneously, but it might not be sufficient to have each building only be watched by a single agent, in case they're taken out. As such, M would like to ask himself ~Q~ ~(1 \le Q \le 10)~ questions, with the ~i~-th one asking "What's the minimum cost to hire agents such that each suspicious building is in sight of at least ~C_i~ ~(1 \le C_i \le M)~ of them, if this is possible at all?". Can you help M answer each of these questions, for the sake of the MI6 fundraising department? If it's impossible to have each building covered by at least ~C_i~ agents, you should output -1 instead. Otherwise, the total cost (in dollars) may be quite large, so you only need to output it modulo ~10^9 + 7~.

Subtasks

In test cases worth ~4/35~ of the points, ~N \le 10~ and ~M \le 10~.
In test cases worth another ~5/35~ of the points, ~N \le 100~ and ~M \le 100~.
In test cases worth another ~8/35~ of the points, ~N \le 2\,000~ and ~M \le 2\,000~.

Input Specification

The first line of input consists of three space-separated integers ~N~, ~M~, and ~Q~.
The next ~N~ lines each consist of a single integer ~B_i~, for ~i = 1 \dots N~.
The next ~M~ lines each consist of two space-separated integers ~A_i~ and ~R_i~, for ~i = 1 \dots M~.
The next ~Q~ lines each consist of a single integer ~C_i~, for ~i = 1 \dots Q~.

Output Specification

Output ~Q~ lines, one integer per line. The ~i~-th line (for ~i = 1 \dots Q~) should consist of the answer to the ~i~-th query (modulo ~10^9 + 7~) or -1 if it's impossible.

Sample Input

2 4 3
10
20
14 5
22 11
0 1
15 5
1
2
3

Sample Output

6
22
-1

Explanation

If M hires agents ~1~ and ~2~ (for a cost of ~2^1 + 2^2 = 6~ dollars), each building will be in sight of a single agent, which is just enough to satisfy the first question. Hiring agents ~1~, ~2~, and ~4~ will allow each building to be in sight of at least two agents. It's impossible to have each building be in sight of three or more agents.