Hôm nay kuroni được học về tổ hợp tuyến tính. Trước khi kết thúc buổi học, thầy giáo ra một câu đố như sau:

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một số nguyên dương ~x~ được gọi là đẹp nếu tồn tại một bộ ~n~ số nguyên không âm ~v_1, v_2, ..., v_n~ thỏa mãn ~x = a_1 \cdot v_1 + a_2 \cdot v_2 + \cdots + a_n \cdot v_n~.

Gọi ~b~ là tập hợp tất cả các số đẹp sắp xếp theo thứ tự tăng dần. Thầy giáo có ~q~ câu hỏi, mỗi câu hỏi thầy giáo yêu cầu học sinh tìm giá trị của số thứ ~k~ trong dãy ~b~.

Cả lớp đang im lặng vì gặp câu hỏi khó, bỗng kuroni thấy buồn đi vệ sinh. Anh ấy đứng lên, giơ tay nói to: "Em..." Chưa kịp nói dứt câu, thầy giáo đã mừng rỡ, ngay lập tức gọi kuroni lên bảng. Không muốn mất mặt trước cả lớp mà tình thế lại vô cùng cấp bách, anh ấy đã cầu cứu bạn cùng bàn. Hãy trợ giúp kuroni trả lời các câu hỏi của thầy nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của dãy ~a~ và ~q~ (~1 \le q \le 3 \cdot 10^5~) — số câu hỏi của thầy giáo.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6, \sum_{i = 1}^n a_i \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~k~ mô tả các câu hỏi của thầy giáo ~(1 \leq k \leq 10^9)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho câu hỏi thứ ~i~.

Subtask

• ~5\%~ số test có ~n = 1~.

• ~10\%~ số test khác có ~1 \leq a_1, a_2, ...,a_n \leq 10~.

• ~15\%~ số test khác có ~k \leq 5000~ trong mọi câu hỏi.

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 8
5 3 11
1
2
8
9
6
5
14
23

Sample Output 1

3
5
12
13
10
9
18
27