floors

Problem Description

Assume that you are the manager of Kitty Hotel, where they provide accommodation for cats on vacation. The hotel has n rooms in total, labelled from 1 to n for convenience.

There is exactly 1 room in each floor, with the i_th room on the i_th floor. However, there is no booking system and the manager only manages the total number of cats that enter the hotel, making sure it is less than or equal to the number of rooms the hotel has.

Each cat that enters the hotel will take the lift to a certain floor, x. If that floor is vacant, it will occupy that floor. However, if that floor isn't vacant, it will walk down the floors until it finds a floor that is vacant and occupy it. In the event that a cat reaches floor 1 and the room there is still occupied, it will then take the lift up to the n_th floor and continue walking downwards until it encounters a vacant floor.

Given the number of cats, c and the floor each cat takes the lift to, determine which floor does it eventually occupy, provided that they arrive in chronological order.

Input

The first line of input will consists of 2 integers, n followed by c

Subsequent c lines will consist of 1 integer each, which is the floor the cat took the lift to.

Output

For each cat, output a single integer indicating the floor it eventually occupies.

Limits

Subtask 1 (30%): 0 ≤ n, c ≤ 1000

Subtask 2 (30%): 0 ≤ n, c ≤ 200000

Subtask 3 (40%): 0 ≤ n ≤ 10000000, 0 ≤ c ≤ 2000000

Sample Input

5 5
2
2
2
5
5

Sample Output

2
1
5
4
3