Marin là người tốt, vì thế anh quyết định tổ chức ~Q~ bữa tiệc cho ~N~ người bạn của anh ấy, và đương nhiên, mọi người đều là những cp-er "siu vjp pro". Đồ uống duy nhất được phục vụ trong mỗi buổi tiệc sẽ là dzumbus - hỗn hợp của cola và nước gừng.

Và vì là người tốt nên Marin biết từng người bạn của anh ấy muốn uống bao nhiêu dzumbus trong bữa tiệc đó để họ được "thoải mái". Anh ấy cũng biết chuyện sẽ có ~M~ cặp những người bạn sẽ bắt đầu trao đổi về kì thi ~COCI~ vừa qua trong suốt mỗi buổi nếu cả hai người trong cặp đó đều "thoải mái".

Khi một người ~A~ chia sẻ cách làm của họ cho ~B~ thì ~B~ cũng chia sẻ lại cách làm của họ cho ~A~. Từ đó ~M~ cặp được hình thành sao cho: trong suốt buổi tiệc, với thứ tự bất kì của các cuộc trao đổi, không xảy ra trường hợp cách làm của ~A~ được chia sẻ ngược lại với anh ấy. Tại mỗi buổi tiệc Marin sẽ chọn cách chia đồ uống sao cho tối đa hóa được số người trao đổi ít nhất một lần trong buổi tiệc đó. Nhiệm vụ của bạn là tính số người sẽ trao đổi cách làm của họ ít nhất một lần trong mỗi bữa tiệc trong ~Q~ bữa tiệc.

Input

Dòng đầu tiên gồm hai số nguyên ~N~, ~M~ lần lượt là số người bạn của Marin và số cặp sẽ thảo luận khi họ thấy "thoải mái".

Dòng thứ hai gồm ~N~ số nguyên ~D_i~, số lượng dzumbus mà người bạn thứ ~i~ cần uống để "thoải mái".

Ở dòng thứ ~i~ trong ~M~ dòng tiếp theo, chứa hai số nguyên ~A_i~ và ~B_i~ ~(A_i \neq B_i)~.

Dòng tiếp theo chứa một số nguyên ~Q~ là số bữa tiệc của Marin.

~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~S_i~ là tổng số dzumbus sẽ có trong bữa tiệc thứ ~i~.

Output

In ra ~Q~ dòng, mỗi dòng là số người sẽ trao đổi được cách làm của mình với người khác.

Phân bố điểm

Ở mọi subtask điều kiện sau luôn được đảm bảo: ~0 \le M < N \le 1000~, ~1 \le Q \le 2 \cdot 10^{5}~, ~1 \le D_i, S_i \le 10^{9}~.

Subtask 1 gồm 2 test: ~M = N - 1~, ~1 \le S_i \le 1000~ và mỗi người bạn của Marin sẽ ghép đôi để trao đổi với tối đa hai người khác.

Subtask 2 gồm 3 test: ~M = N - 1~ và mỗi người bạn của Marin sẽ ghép đôi để trao đổi với tối đa hai người khác.

Subtask 3 gồm 3 test: ~N \le 100~.

Subtask 4 gồm 3 test: Không có ràng buộc gì thêm.

Examples

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 output 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

Giải thích cho ví dụ thứ ba:

• Ở bữa tiệc đầu tiên, Marin quyết định cho những người bạn với chỉ số 1, 2, 3, 7, 9, 10, 12 và 13 được thoải mái. và họ uống tổng cộng 45 đơn vị dzumbus.