Marin là một người tốt bụng, anh ấy sẽ tổ chức ~Q~ bữa tiệc cho ~N~ người bạn của mình, tất cả đều là lập trình viên thi đấu. Loại đồ uống duy nhất được phục vụ tại các bữa tiệc của anh ấy sẽ là džumbus — một hỗn hợp của Coke và nước gừng. Đối với mỗi người bạn của mình, Marin biết lượng džumbus họ cần uống để thư giãn. Anh ấy cũng biết rằng có ~M~ cặp người trong số bạn bè của anh ấy mà nếu cả hai đều thư giãn, họ sẽ bắt đầu trao đổi các lời giải của các bài toán COCI trước đây (vì không có các giải thích chính thức được công bố).

Khi một người ~A~ chia sẻ các lời giải của họ với người ~B~, người ~B~ có thể quyết định chia sẻ các lời giải đó theo cùng một cách, nhưng cũng được biết rằng ~M~ cặp này được hình thành theo cách mà không thể nào những lời giải đó sẽ quay lại người ~A~ trong bữa tiệc đó, bất kể thứ tự trao đổi diễn ra như thế nào.

Marin đã chuẩn bị lượng džumbus khác nhau cho mỗi bữa tiệc. Trong mỗi bữa tiệc, anh ấy sẽ phân phối đồ uống sao cho tối đa số người sẽ ít nhất một lần trao đổi các lời giải với một người khác trong bữa tiệc đó.

Nhiệm vụ của bạn là xác định số người sẽ trao đổi các lời giải trong mỗi bữa tiệc.

Input

• Dòng đầu tiên chứa các số nguyên ~N~ và ~M~ từ mô tả bài toán.
• Dòng thứ hai chứa ~N~ số nguyên cách nhau bởi dấu cách ~D_i~, lượng džumbus cần thiết để thư giãn bạn bè của Marin, theo thứ tự từ bạn số ~1~ đến bạn số ~N~.
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa hai số nguyên ~A_i~ và ~B_i~ ~(A_i \ne B_i)~, biểu thị một cặp bạn bè từ mô tả bài toán.
• Dòng tiếp theo chứa một số nguyên ~Q~ từ mô tả bài toán.
• ~Q~ dòng tiếp theo chứa một số nguyên ~S_i~ biểu thị tổng lượng džumbus sẽ được phục vụ tại bữa tiệc thứ ~i~.

Output

In ra số người sẽ trao đổi các lời giải trong mỗi bữa tiệc. Câu trả lời cho mỗi bữa tiệc nên được in ra trong một dòng riêng biệt. Lưu ý rằng các bữa tiệc độc lập với nhau.

Chú ý

• Trong tất cả các phần kiểm tra, giữ ~0 \leq M < N \leq 1000, 1 \leq Q \leq 200000, 1 \leq D_i \leq 10^9~ và ~1 \leq S_i \leq 10^9~.
• ~20~ điểm thỏa mãn ~M = N - 1~, ~S_i \leq 1000~. Các bạn của Marin sẽ được ghép đôi theo cách mà mỗi người bạn sẽ trao đổi lời giải của họ với tối đa hai người khác.
• ~30~ điểm thỏa mãn các bạn của Marin sẽ được ghép đôi theo cách mà mỗi người bạn sẽ trao đổi lời giải của họ với tối đa hai người khác.
• ~30~ điểm thỏa mãn ~N \leq 100~.

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

Giải thích

Trong test thứ 3, tại bữa tiệc đầu tiên, Marin đã quyết định làm thư giãn những người bạn có chỉ số 1, 2, 3, 7, 9, 10, 12 và 13. Họ đã uống tổng cộng 45 đơn vị džumbus.