Mùa hè sắp đến, mùa của những hoạt động ngoài trời.

Sau kỳ thi cuối kỳ mệt mỏi, Rotund đã đăng ký làm tình nguyện viên cho trại hè của trung tâm Code Dream tổ chức. Công việc của cậu vốn rất đơn giản, chỉ cần phân nhóm những học sinh tham gia trại hè thành từng đội có số người giống nhau.

Có tổng cộng ~n~ trường đăng ký tham gia trại hè, với tổng số ~k~ học sinh. Với mong muốn học sinh có trải nghiệm trại hè vui vẻ và đặc sắc, bà chủ Code Dream yêu cầu Rotund phải phân nhóm sao cho không có 2 học sinh nào trong một đội thuộc cùng một trường (~x~ người trong một đội phải đến từ ~x~ trường khác biệt, để học sinh có cơ hội giao lưu với các bạn mới nhiều hơn).

Vì số lượng học sinh giữa các trường có thể có sự chênh lệch rất lớn nên lựa chọn số lượng người của từng đội trở thành một vấn đề, vì nếu chia không tốt thì rất nhiều học sinh sẽ không được tham gia. Bà chủ đã đưa ra ~q~ phương án chọn số lượng học sinh cho một đội và yêu cầu Rotund tính xem có thể tạo được tối đa bao nhiêu đội với từng phương án. Rotund cần tìm ra phương pháp xử lý vấn đề này nhanh nhất có thể để trung tâm Code Dream có thể sớm chuẩn bị tổ chức kế hoạch trại hè.

Yêu cầu

Cho số lượng trường ~n~, tổng số học sinh ~k~, số truy vấn ~q~ và số học sinh thuộc từng trường ~a_i~. Với mỗi truy vấn, cho số học sinh trong một đội là ~x~, hãy tính số lượng đội tối đa có thể tạo được.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~n~, ~k~, ~q~ ~(1≤n≤10^6, 1≤k≤10^{18}, 1≤q≤10^3)~ lần lượt là số lượng trường đăng ký, tổng số học sinh và số truy vấn, cách nhau một dấu cách.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1≤a_i≤10^{18},~ tổng dãy ~a_i~ bằng ~k)~, là số lượng học sinh thuộc từng trường cách nhau một dấu cách.
• ~q~ dòng còn lại, mỗi dòng chứa một số nguyên dương ~x~ ~(1≤x≤n)~ là số học sinh một đội.

Output

• ~q~ dòng, mỗi dòng chứa một số nguyên là số lượng đội tối đa có thể tạo được.

Sample Input 1

3 6 1
2 2 2
2

Sample Output 1

3

Giải thích

Có 3 trường tham gia, tổng 6 học sinh với số lượng học sinh của mỗi trường đều là 2 học sinh.

Có thể phân được 3 đội như sau: ~[1, 2]~, ~[1, 3]~, ~[2, 3]~.

Sample Input 2

3 6 2
1 4 1
2
3

Sample Output 2

2
1

Giải thích

Truy vấn 1: 2 người một đội. Có thể tạo được 2 đội như sau: ~[1, 2]~, ~[2, 3]~.

Truy vấn 2: 3 người một đội. Chỉ có thể tạo được 1 đội như sau: ~[1, 2, 3]~.

Subtask

• Có 30% số test ứng với 30% số điểm có ~q=1, x=2~;
• Có 30% số test ứng với 30% số điểm có ~1≤q≤5, 1≤k≤10^5~;
• Có 20% số test ứng với 20% số điểm có ~1≤q≤5, 1≤n≤10^5~;
• 20% số test còn lại tương ứng với 20% số điểm không có giới hạn gì thêm.