Để chuẩn bị cho kỳ thi Olympic Tin học Miền Trung - Tây Nguyên, bạn Việt lên kế hoạch ôn tập \(N\) chuyên đề Cấu trúc dữ liệu và Giải thuật. Các chuyên đề được đánh số từ \(1\) đến \(N\). Chỉ số kỹ năng hiện tại của Việt ở chuyên đề thứ \(i\) được đánh giá bằng một số nguyên không âm \(a_i\). Việt nhận định rằng năng lực thi đấu thực tế của mình bị giới hạn bởi chuyên đề yếu nhất. Do đó, năng lực của Việt được xác định bằng chỉ số kỹ năng thấp nhất trong tất cả các chuyên đề, tức là \(\min(a_1, a_2, \dots, a_N)\).

Trong quá trình luyện tập, với mỗi giờ học, Việt có thể chọn một chuyên đề bất kỳ và làm bài tập để nâng chỉ số kỹ năng của mình ở chuyên đề đó lên thêm \(1\) đơn vị.

Có \(Q\) kỳ thi thử sắp diễn ra. Các kỳ thi này được xét hoàn toàn độc lập với nhau (nghĩa là chỉ số kỹ năng của Việt trước mỗi kỳ thi luôn bắt đầu lại từ mảng \(a\) ban đầu). Đối với kỳ thi thứ \(j\), Việt có quỹ thời gian là \(k_j\) giờ để ôn tập.

Yêu cầu: Cho biết năng lực lớn nhất mà Việt có thể đạt được trong từng kỳ thi, giả sử Việt có chiến thuật phân bổ thời gian ôn tập tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 4 \cdot 10^5\)) lần lượt là số lượng chuyên đề và số lượng kỳ thi.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^9\)) là chỉ số kỹ năng ban đầu của Việt ở các chuyên đề.
• Dòng thứ \(j\) trong số \(Q\) dòng tiếp theo chứa một số nguyên \(k_j\) (\(1 \le k_j \le 10^{18}\)) là số giờ ôn tập Việt có trước kỳ thi thứ \(j\).

Output

• In ra \(Q\) dòng, mỗi dòng là một số nguyên duy nhất thể hiện năng lực lớn nhất đạt được tương ứng với kỳ thi thứ \(j\).

Example

5 3
2 1 4 3 6
2
5
10

2
3
5

Scoring

• Subtask \(1\) (\(15\) điểm): \(N, Q \le 100\) và \(k_j \le 100\) với mọi \(j = 1, 2, \dots, Q\).
• Subtask \(2\) (\(15\) điểm): \(N, Q \le 300\).
• Subtask \(3\) (\(25\) điểm): \(N, Q \le 1500\).
• Subtask \(4\) (\(25\) điểm): \(a_i \le 100\) với mọi \(i = 1, 2, \dots, N\).
• Subtask \(5\) (\(20\) điểm): Không có ràng buộc nào thêm.