Cho một dãy ~n~ số nguyên có giá trị lần lượt từ 1 đến ~n~. Bạn được thực hiện ~m~ thao tác, mỗi thao tác sẽ xóa một số khỏi dãy tại một vị trí bất kỳ. Sau mỗi thao tác xóa thì tất cả các số đằng sau chưa bị xóa sẽ được dồn về phía trước.

Yêu cầu: Cho biết vị trí cần xóa của ~m~ thao tác, viết chương trình xác định số bị xóa trong mỗi thao tác. Nếu trong một thao tác không có số nào bị xóa thì ghi ra số 0.

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên lần lượt là ~n,m~ ~(1≤ n,m ≤ 300000)~.
• Dòng thứ 2 ghi ~m~ số nguyên lần lượt là các vị trí cần xóa.

Dữ liệu ra:

• Gồm ~m~ dòng, dòng thứ ~i~ là số bị xóa ở lượt thứ ~i~. ~(1≤ i ≤ n)~

Ví dụ:

Input

6 3
2 4 6 

Output

2
5
0 

Ràng buộc:

• 30% số test có ~n≤100~.
• 30% số test có ~101≤n≤10000~.
• 40% số test có ~10001≤n≤300000~.