Džumbus

Time limit1sMemory limit512 MB

Summary

Given a forest of N friends with drink thresholds, and Q queries each supplying a total drink S, find the maximum number of people who exchange solutions.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, DFS, Binary search
Solved: No attempts yet

Problem

Marin is a good man, so he will organize Q parties for his N friends, all of whom are competitive programmers. The only drink served at his parties is džumbus, a mixture of Coke and ginger juice.

For each of his friends, Marin knows the amount of džumbus they need to drink in order to relax. He also knows that there are M pairs of people among his friends such that, if both of them are relaxed, they will begin to exchange the solutions of past COCI problems, since there are no published editorials. When a person A shares their solutions with person B, person B may decide to share those solutions in the same manner, but the M pairs are formed in a way that makes it impossible for those solutions to get back to person A during that party, regardless of the order in which exchanges take place.

Marin has prepared different amounts of džumbus for each party. During each party, he will distribute the drink in a way that maximizes the number of people who will exchange their solutions with another person at least once at that party.

Your task is to determine the number of people who will exchange their solutions for each of the Q parties.

Input

The first line contains the integers N and M from the problem statement.

The second line contains N space-separated integers Di, the amounts of džumbus needed to relax Marin's friends, given in order from friend 1 to friend N.

The i-th of the next M lines contains two integers Ai and Bi (Ai ≠ Bi), denoting a pair of friends from the problem statement.

The next line contains the integer Q from the problem statement.

The next Q lines contain a single integer Si, which represents the total amount of džumbus that will be served at the i-th party.

Output

Output the number of people who will exchange their solutions for each of the Q parties. The answer for each party should be given on a separate line. The parties are independent of each other.

Constraints

In all subtasks, 0 ≤ M < N ≤ 1000, 1 ≤ Q ≤ 2 · 105, 1 ≤ Di ≤ 109, and 1 ≤ Si ≤ 109.

Example 1

Input:

Expected output:

Example 2

Input:

Expected output:

0
2
2

Example 3

Input:

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23

Expected output:

8
7
5

Examples3

Example 1
Input
```
1 0
1000
1
1000
```
Expected output
```
0
```
Example 2
Input
```
3 2
1 2 3
1 2
1 3
3
2
3
5
```
Expected output
```
0
2
2
```

Example 3

Input

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23

Expected output

8
7
5