Phần tử thiếu

Alice là một học sinh có đam mê làm việc với các con số. Cậu sưu tầm và lưu lại danh sách các số nguyên dương mà mình thích và gọi đó là những số nguyên dương ``đẹp''.

Hiện tại, Alice đang sở hữu một danh sách \(A\) gồm \(N\) số nguyên dương đẹp: \(A_1, A_2, \ldots, A_N\), các giá trị đôi một khác nhau và được sắp xếp tăng dần (\(A_1 < A_2 < \ldots < A_N\)). Các số nguyên dương không xuất hiện trong danh sách \(A\) được gọi là các ``phần tử thiếu''.

Alice cần trả lời \(Q\) truy vấn độc lập, mỗi truy vấn cho một số nguyên dương \(k\). Hãy xác định giá trị phần tử thiếu thứ \(k\) khi liệt kê các phần tử thiếu của danh sách \(A\) theo thứ tự tăng dần.

Yêu cầu: Bạn hãy giúp Alice trả lời \(Q\) truy vấn trên.

Input

Dữ liệu vào có cấu trúc sau:

• Dòng 1: Chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)), lần lượt là số lượng phần tử trong danh sách và số lượng các truy vấn; các giá trị được ghi cách nhau một dấu cách.

• Dòng 2: Chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^{18}\)); các giá trị được ghi cách nhau một dấu cách. Dữ liệu đảm bảo danh sách \(A\) được sắp xếp tăng nghiêm ngặt.

• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k_i\) (\(1 \le k_i \le 10^{18}\), \(1 \le i \le Q\)), tương ứng với câu hỏi tìm phần tử thiếu thứ \(k_i\).

Ràng buộc:

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm: \(1 \le N, Q \le 2 \cdot 10^3\);

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm: \(1 \le A_i \le 10^6\) (\(1 \le i \le N\));

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm: không có ràng buộc gì thêm.

Output

In ra theo cấu trúc sau:

Gồm \(Q\) dòng: Dòng thứ \(i\) ghi một số nguyên \(t\) là giá trị phần tử thiếu thứ \(k_i\) (\(1 \le i \le Q\)) trong danh sách \(A\).

Example

Input:

5 3
1 3 9 12 17
2
9
19

Output:

4
13
24

Note

Phần tử thiếu thứ \(2\) là \(4\) (các phần tử thiếu là \(2, 4, 5, \ldots\)).

Phần tử thiếu thứ \(9\) là \(13\).

Phần tử thiếu thứ \(19\) là \(24\).