Problem D
Menu Updates

Egdirbhtel is running a successful restaurant, and every day has either a new recipe idea or retires an old one. The restaurant menu uses a unique number to represent each menu item in order to help customers order items efficiently. Unfortunately, the clientele find it confusing when a given number represents a menu item, Egdirbhtel retires that item, and soon afterwards adds a new item represented by that same number.

Egdirbhtel has come up with a solution: every positive integer starts out as available, and becomes reserved when it starts representing a new menu item. When retiring a menu item on day $i$, the number that represented it stays reserved for $d$ days, until it becomes available again on day $i+d$. When Egdirbhtel adds a new menu item, the smallest available positive integer on that particular day will represent it.

Because of the daily menu changes, Egdirbhtel would like you to come up with a computer program to quickly determine which number will represent each new item on the menu according to the above process.

The restaurant starts out with an empty menu, which might become empty again on some days (in which case the angry customers will convince Egdirbhtel to add something new to the next day’s menu).

Input

Input begins with two space-separated integers $1 \leq d \leq U \leq 2 \cdot 10^5$, where $d$ indicates the minimum number of days that need to pass after retiring a menu item before its number can represent a new item, and $U$ indicates the total number of menu updates to process, with exactly one menu update (adding a new item to the menu or retiring an old one) per day.

The next $U$ lines each consist of either the single letter a, signifying that Egdirbhtel adds a new menu item that day, or the letter r followed (space-separated) by the number representing the menu item that Egdirbhtel retires that day. This number will always represent a menu item that the restaurant had at that time according to the process described above.

Output

For every input line consisting of an a, output a line consisting of the number representing the newly-added menu item. (Since the menu starts out empty, the output will always begin with a 1.)

3 3
a
a
a

1
2
3

1 3
a
r 1
a

1
1

2 5
a
a
r 2
a
a

1
2
3
2