Watson is responsible for distribution of patients in a ward of a hospital. The ward contains \textbf{N} places, which are lined up in a row and sequentially numbered from \textbf{1} to \textbf{N}. 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. \InputFile The first line contains \textbf{2} integers: \textbf{N} -- numbers on places in the ward and \textbf{Q} -- number of entries in the log. Following \textbf{Q} lines contain entries from the log: "\textbf{0}" -- admission, "\textbf{1 X}" - discharging of the patient which has been admitted according to the log's entry number \textbf{X} (numeration is \textbf{1}-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. \textbf{0} ≤ \textbf{N}, \textbf{Q} < \textbf{10^5}. \OutputFile You need to print place number for every admission in the log.