Dãy con cực đại

Bạn được cho một dãy \(A\) gồm \(N\) số nguyên, đánh số từ \(1\) đến \(N\).

Với một số \(X\) được cho, bạn hãy tìm tập \(k\) số trong dãy \(A\) sao cho điều kiện sau được thỏa mãn:

• Gọi \(k\) chỉ số lần lượt là \(1 \le i_1 \le i_2 \le \ldots \le i_k \le N\).
• \(X + a[i_1] \ge 0\)
• \(X + a[i_1] + a[i_2] \ge 0\)
• …
• \(X + a[i_1] + a[i_2] + \ldots + a[i_k] \ge 0\)

Yêu cầu tìm \(k\) lớn nhất với \(X\) bất kì.

Để làm bài toán hóc búa hơn, bạn được cho \(Q\) truy vấn, mỗi truy vấn là số \(X\) mà bạn phải trả lời.

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(Q\) (\(1 \le N \le 2 \times 10^3, 1 \le Q \le 3 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \leq a_i \leq 10^9\)).
• Dòng thứ ba chứa \(Q\) số nguyên \(X_1, X_2, \dots, X_K\) (\(-10^{14} \leq X_i \leq 10^{14}\)).

Output

In ra \(Q\) số nguyên là đáp án của bài toán trên một dòng.

Example

7 3
-3 0 4 -7 -4 -5 4
2 11 15

4 6 7 

8 4
-2 -2 0 7 1 -9 9 -7
1 1 20 3

6 6 8 7 

Scoring

• Subtask 1 (13% số điểm): Dãy \(A\) tăng hoặc giảm dần.
• Subtask 2 (10% số điểm): \(N \leq 20\), \(Q \leq 30\).
• Subtask 3 (15% số điểm): \(N \leq 20\).
• Subtask 4 (25% số điểm): \(Q \leq 3000\).
• Subtask 5 (37% số điểm): Không có ràng buộc gì thêm.