Delicious delicious beer džumbus.

Marin is a good man, so he'll organize ~Q~ parties for his ~N~ friends, all of whom are competitive programmers. The only drink that is going to be served at his parties will be 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~, the person ~B~ may decide to share those solutions in the same manner, but it is also known that ~M~ pairs are formed in a way that it is impossible that those solutions will get back to person ~A~ during that party, regardless of the order in which exchanges took place. Marin has prepared different amounts of džumbus for each party. During each party, he will distribute the drink in a way which maximizes the number of people that will at least once exchange their solutions with another person at that party. Your task is to determine the number of people that will exchange their solutions for each of the ~Q~ parties.

Input

The first line contains integers ~N~ and ~M~ from the task description. The second line contains ~N~ space separated integers ~D_i~, the amounts of džumbus needed to relax Marin's friends, given in order from a friend number ~1~ to a friend number ~N~. The ~i~th of the next ~M~ lines contains two integers ~A_i~ and ~B_i~ ~(A_i \ne B_i)~, denoting a pair of friends from the task description. The next line contains an integer ~Q~ from the task description. The next ~Q~ lines contain a single integer ~S_i~ which represents the total amount of džumbus that is going to be served at ~i~th party.

Output

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

Scoring

In all subtasks, it holds ~0 \le M < N \le 1000~, ~1 \le Q \le 2 \times 10^5~, ~1 \le D_i \le 10^9~, and ~1 \le S_i \le 10^9~.

Subtask	Score	Constraints
1	~20~	~M=N-1~, ~1 \le S_i \le 1000~, Marin's friends will be paired up in a way that each friend will exchange their solutions with at most two other people.
2	~30~	~M=N-1~, Marin's friends will be paired up in a way that each friend will exchange their solutions with at most two other people.
3	~30~	~N \le 100~
4	~30~	No additional constraints.

Sample Input 1

1 0
1000
1
1000

Sample Output 1

0

Sample Input 2

3 2
1 2 3
1 2
1 3
3
2
3
5

Sample Output 2

0
2
2

Sample Input 3

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

Sample Output 3

8
7
5

Explanation of Sample Output 3

At the first party, Marin decided to relax friends with indices 1, 2, 3, 7, 9, 10, 12, and 13. They have drunk a total of 45 units of džumbus.