Seats in the subway
本题没有可用的提交语言。
Description
Vasily likes to use his phone in the subway. But he doesn't want anyone to see his phone screen. Vasily asked you to help all those who like to sit alone.
Consider a subway car that has one row of $n$ seats, numbered from $1$ to $n$, initially all seats are empty. $k$ consecutive requests are received. There are two types of requests:
- "$-x$". Passenger who entered the $x$-th left. It is guaranteed that such a passenger is in the subway.
- "$+$". A new passenger has arrived. It is guaranteed that there is at least one free seat.
For each request of the second type, you should display a number of free seat. The distance to the nearest occupied seat should be maximum. If there are several such seats, you should display the seat with the minimum number. Starting from the next request, this seat is considered occupied until it is freed.
The first line contains two integers $n$ and $k$ — the number of seats and the number of requests ($1 \leq n \leq 10^{18}$; $1 \leq k \leq 10^5$). The next $k$ lines contain queries, one on each line.
For each request "$+$" print the number of the seat where the corresponding passenger will sit.
Input
The first line contains two integers $n$ and $k$ — the number of seats and the number of requests ($1 \leq n \leq 10^{18}$; $1 \leq k \leq 10^5$). The next $k$ lines contain queries, one on each line.
Output
For each request "$+$" print the number of the seat where the corresponding passenger will sit.
5 9
+
-1
+
+
+
+
-4
+
+
5 8
+
+
+
+
+
-4
-3
+
1
1
5
3
2
3
4
1
5
3
2
4
2