# 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`.)

Sample Input 1 | Sample Output 1 |
---|---|

3 3 a a a |
1 2 3 |

Sample Input 2 | Sample Output 2 |
---|---|

1 3 a r 1 a |
1 1 |

Sample Input 3 | Sample Output 3 |
---|---|

2 5 a a r 2 a a |
1 2 3 2 |