Cho hai số nguyên dương ~n~, ~q~ và dãy số nguyên ~a_1, a_2, \dots, a_n~ (~a_i = i~; ~i = 1 \dots n~) và ~q~ thao tác được thực hiện theo thứ tự từ 1 đến ~q~. Với thao tác thứ ~i~ (~1 \leq i \leq q~) bạn được cho một số nguyên ~x_i~ (~1 \leq x_i \leq n~) và thực hiện yêu cầu hoán đổi giá trị của số có giá trị ~x_i~ với số đứng liền sau nó trong dãy số. Nếu ~x_i~ đang đứng cuối dãy số thì hoán đổi với số đứng liền trước nó.

Input

• Dòng đầu tiên ghi lần lượt hai số nguyên ~n~, ~q~ (~1 \leq n, q \leq 10^5~);
• ~q~ dòng tiếp theo, dòng thứ ~i~ (~1 \leq i \leq q~) ghi số nguyên ~x_i~ (~1 \leq x_i \leq n~)

Output

• In ra dãy số ~a_1, a_2, \dots, a_n~ sau khi thực hiện lần lượt ~q~ thao tác trong dữ liệu vào.

Sample Test

Input

5 3
3
5
1

Output

2 1 4 5 3

Giải thích: Dãy số ban đầu: ~1, 2, 3, 4, 5~

• Truy vấn ~x_1 = 3~: hoán đổi ~a_3~ với ~a_4 \rightarrow 1, 2, 4, 3, 5~
• Truy vấn ~x_2 = 5~: hoán đổi ~a_5~ với ~a_4 \rightarrow 1, 2, 4, 5, 3~
• Truy vấn ~x_3 = 1~: hoán đổi ~a_1~ với ~a_2 \rightarrow 2, 1, 4, 5, 3~

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có ~n, q \leq 2000~;
• Có 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm.