Accomodation#5224
Watson is responsible for distribution of patients in a ward of a hospital. The ward contains places, which are lined up in a row and sequentially numbered from to . To minimize morbidity patients should be placed as far from each other or ward's entry as possible, and it is not allowed to relocate them. Watson has access to admission and discharging log. For each admission, Watson needs to find a place for new patient's allocation. In order to do this, Watson is to select the most distant from other patients place. If there are several such places, he should minimize the number of patients located at this minimal distance. If there are still several places, he should choose the most distant place from entry.
The first line contains integers: – number of places in the ward and – number of entries in the log. Following lines contain entries from the log: "" – admission, " " - discharging of the patient which has been admitted according to the log's entry number (numeration is -based and includes both admissions and dischargings).
It is guaranteed that the patient that is being discharged is present in the hospital. It is also guaranteed that for every admission there will be at least one place available.
0 \le N, Q < 10^5.
You need to print place number for every admission in the log.
Example 1