Với một số nguyên dương ~x \ge 2~, gọi ~f(x)~ là ước số nguyên tố lớn nhất của ~x~.

Yêu cầu: Cho số ~n~ và ~q~ câu hỏi, mỗi câu hỏi cho bởi số nguyên dương ~k~. Bạn hãy cho biết trong phạm vi từ 2 tới ~n~ có bao nhiêu giá trị ~x~ mà ~f(x) \le k~.

Input

• Dòng 1 chứa hai số nguyên dương ~n, q~ cách nhau bởi dấu cách (~2 \le n \le 10^6; q \le 10^6~).
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~ ứng với một câu hỏi (~2 \le k \le n~).

Output

Ghi ra ~q~ dòng, ứng với mỗi câu hỏi, ghi ra một số nguyên trên một dòng là đáp số của câu hỏi tương ứng.

Sample Input 1

10 4
2
5
3
8

Sample Output 1

3
8
6
9

Từ 2 tới 10 có:

• 3 số ~x~ có ~f(x) \le 2~: 2, 4, 8
• 8 số ~x~ có ~f(x) \le 5~: 2, 3, 4, 5, 6, 8, 9, 10
• 6 số ~x~ có ~f(x) \le 3~: 2, 3, 4, 6, 8, 9
• 9 số ~x~ có ~f(x) \le 8~: 2, 3, 4, 5, 6, 7, 8, 9, 10

Subtasks

• 60% số điểm ứng với các test có ~n \le 10^4; q \le 10~.
• 40% số điểm ứng với test không có ràng buộc bổ sung.

Ba vận động viên A, B, C thuộc cùng một đội tham gia giải chạy tiếp sức. Đường đua được chia làm ~n~ chặng đánh số từ 1 tới ~n~ dọc theo chiều dài đường đua, chặng thứ ~i~ có độ dài ~a_i~ mét.

Căn cứ vào thực lực của các vận động viên, huấn luyện viên của đội đề ra chiến thuật chạy thỏa mãn ba yêu cầu sau:

• A sẽ chạy những chặng đầu tiên, tiếp theo là B chạy những chặng kế tiếp, kết thúc là C chạy những chặng cuối cùng.
• Mỗi vận động viên phải chạy nguyên một số (có thể bằng 0) chặng liên tiếp.
• Quãng đường chạy của A ngắn hơn hoặc bằng quãng đường chạy của B, quãng đường chạy của B ngắn hơn hoặc bằng quãng đường chạy của C.

Yêu cầu: Dù A là vận động viên yếu nhất và phải chạy quãng đường ngắn nhất nhưng huấn luyện viên cũng muốn A coi cuộc đua là một cơ hội luyện tập. Vì vậy huấn luyện viên muốn nhờ bạn phân chia chặng đường chạy cho ba vận động viên thỏa mãn cả ba yêu cầu trên mà độ dài quãng đường chạy của A là lớn nhất có thể.

Input

• Dòng 1 chứa số nguyên dương ~n~ (~3 \le n \le 10^6~).
• Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (~a_i \le 10^6~ với mọi ~i~).

Output

Ghi ra một số nguyên duy nhất là độ dài quãng đường chạy của A theo phương án tìm được.

Sample Input 1

6
1000 2000 3000 1000 4000 2000

Sample Output 1

3000

Giải thích:

• A chạy 2 chặng đầu: ~1000 + 2000 = 3000~
• B chạy 2 chặng tiếp: ~3000 + 1000 = 4000~
• C chạy 2 chặng cuối: ~4000 + 2000 = 6000~

Sample Input 2

8
100 1 2 3 4 5 6 7

Sample Output 2

0

Giải thích: A và B không chạy chặng nào, C chạy hết cả đường đua.

Sample Input 3

9
4 2 1 4 1 9 3 3 3

Sample Output 3

6

Giải thích:

• A chạy 2 chặng đầu: ~4 + 2 = 6~
• B chạy 3 chặng tiếp: ~1 + 4 + 1 = 6~
• C chạy 4 chặng cuối: ~9 + 3 + 3 + 3 = 18~

Sample Input 4

11
9 3 1 8 7 1 3 1 1 7 2

Sample Output 4

13

Subtasks

• 30% số điểm ứng với các test có ~n \le 100~.
• 40% số điểm ứng với các test có ~n \le 5000~.
• 30% số điểm ứng với các test không có ràng buộc bổ sung.

Nhân ngày 1/6, giáo sư X mang tới ~n~ gói kẹo để làm quà cho các bé thiếu nhi trường mầm non SuperKids. Các gói kẹo được đánh số từ 1 tới ~n~, gói thứ ~i~ có ~a_i~ viên kẹo. Tuy nhiên khi đến trường giáo sư mới biết được số các bé thiếu nhi là ~m~ (~m < n~) vì vậy ông cần phân phối lại để có được ~m~ gói có số kẹo bằng nhau để phát cho các bé.

Yêu cầu: Biết rằng trong mỗi giây giáo sư X có thể lấy đúng một viên kẹo từ một gói chuyển sang một gói khác. Hãy cho biết thời gian tối thiểu giáo sư X cần để thu được ~m~ gói kẹo với số kẹo bằng nhau từ ~n~ gói kẹo ban đầu.

Input

• Dòng 1 chứa hai số nguyên dương ~n, m~ (~1 \le m < n \le 10^6~).
• Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~ với mọi ~i~).

Các số trên một dòng cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là số giây tối thiểu giáo sư X cần để thu được ~m~ gói kẹo với số kẹo bằng nhau từ ~n~ gói kẹo ban đầu.

Sample Input 1

4 3
6 3 8 9

Sample Output 1

2

Sample Input 2

6 4
3 8 9 4 3 3

Sample Output 1

1

Sample Input 3

7 5
1 1 2 5 5 5 5

Sample Output 1

4

Subtasks

• 40% số điểm ứng với các test có ~n \le 1000~ và ~a_1, a_2, ..., a_n \le 1000~.
• 30% số điểm ứng với các test có ~n \le 1000~.
• 30% số điểm không có ràng buộc bổ sung.

Có ~n~ chú kiến đánh số từ 1 tới ~n~ đứng quanh một cái hồ hình tròn có chu vi ~m~ mét. Theo chiều kim đồng hồ, sau 1 mét từ chú kiến 1 là chú kiến 2, sau 1 mét từ chú kiến 2 là chú kiến 3, ..., sau 1 mét từ chú kiến ~n~ là chú kiến 1. Các chú kiến xuất phát cùng lúc, di chuyển quanh hồ với tốc độ như nhau.

Với mỗi chú kiến ~i~, ta được biết hai thông tin:

• Ký tự ~c_i~ cho biết hướng đi: ~c_i = '+'~ nếu chú kiến thứ ~i~ đi theo chiều kim đồng hồ, ~c_i = '-'~ nếu chú kiến thứ ~i~ đi ngược chiều kim đồng hồ.
• Số nguyên dương ~d_i~ cho biết độ dài quãng đường mà chú kiến thứ ~i~ sẽ đi.

Nếu hai chú kiến đi ngược chiều gặp nhau, chúng sẽ chạm râu để thực hiện lời chào rồi đi tiếp. Thời gian chào không đáng kể và không ảnh hưởng tới tốc độ cũng như hướng đi của kiến. Lưu ý rằng hai chú kiến có thể gặp và chào nhau nhiều lần. Sau khi chú kiến đi hết quãng đường đã định, nó sẽ rời khỏi vòng hồ và không thực hiện bất kỳ lời chào nào nữa.

Yêu cầu: Với mỗi chú kiến, hãy cho biết trong suốt hành trình đã có bao nhiêu lời chào được chú kiến đó thực hiện (lời chào thực hiện vào đúng thời điểm một trong hai chú kiến kết thúc hành trình cũng được tính nếu có).

Input

• Dòng 1 chứa số nguyên dương ~n~ (~n \le 2 \times 10^5~) và chu vi hồ ~m~ (~m \le 10^9~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ký tự ~c_i~ và số nguyên dương ~d_i~ liền nhau (~|d_i| \le 10^9~).

Output

Ghi ra ~n~ dòng, dòng thứ ~i~ ghi một số nguyên là số lời chào mà chú kiến thứ ~i~ thực hiện trong suốt hành trình của mình.

Sample Input 1

6 5
+ 4
- 5
- 5
+ 5
+ 5
- 3

Sample Output 1

5
6
5
4
5
3

Subtasks

• 30% số điểm ứng với các test có ~n, d_1, d_2, ..., d_n \le 100~.
• 30% số điểm ứng với các test có ~n \le 5000~.
• 20% số điểm ứng với các test có ~d_1 = d_2 = ... = d_n~.
• 20% số điểm ứng với các test không có ràng buộc bổ sung.