ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Поединок с И-Так-Понятно-Кем

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Несмотря на свои неординарные способности, волшебники любят использовать высшую математику. А именно, они любят находить нужную комнату по ее номеру! Но, конечно же, и тут не обошлось без магии.
В Министерстве Магии на двери комнат наложены чары, которые автоматически нумеруют комнаты: стоит ввести в эксплуатацию новую комнату, как на её двери тут же появляется табличка с номером. Новый номер вычисляется как число, на единицу большее максимального существующего на данный момент номера комнаты. Естественно, ранее существовавшие номера при этом не меняются. Первая созданная комната, разумеется, получила номер 1. Если же комната больше не нужна, то её дематериализуют, и все номера комнат, большие номера уничтожаемой комнаты, уменьшаются на единицу. Благодаря этому нумерация комнат всегда остается сплошной.
Гарри Поттеру удалось узнать номера комнат в министерстве, где могут находиться артефакты, обеспечивающие Сами-Знаете-Кому бессмертие. Казалось бы, теперь найти их и уничтожить не составит труда. Но не тут-то было. Благодаря своей связи с Гарри, Волан-де-Морт сразу же узнал про открытие Гарри. Поэтому он перенесся в министерство и стал уничтожать комнату за комнатой. Теперь Гарри, видя номер на двери, не знает, какой у этой комнаты был номер раньше. Но зато он знает, какие номера были на дверях комнат, которые уничтожал и уничтожает его враг (ведь Гарри тоже чувствует все, к чему причастен Волан-де-Морт). Вы должны помочь Гарри! Конечно, никто не просит вас сражаться с Вы-Догадываетесь-Кем, но ведь вы можете помочь Гарри быстрее определить настоящий номер комнаты, около которой он находится.

Исходные данные

В первой строке входа указаны число N - количество комнат в министерстве N (1 ≤ N ≤ 109) и число M (1 ≤ M ≤ 105). Каждая из последующих M строк имеет следующий формат:
<letter> <number>
где <letter> - одна из букв 'D' (Destroy) или 'L' (Look at), а <number> - номер на двери комнаты, которая оказывается уничтоженной в данный момент, или на которую в данный момент смотрит Гарри. Известно, что в процессе битвы будет уничтожено не более 104 комнат.

Результат

Выход должен содержать для каждой строки
L <number>
входных данных настоящий номер (который был до начала всего этого безобразия) комнаты, на которую смотрит Гарри. Числа должны располагаться по одному в строке.

Пример

исходные данныерезультат
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
5
4
6
4
7
Автор задачи: Александр Клепинин, Станислав Васильев
Источник задачи: X командный Чемпионат Урала по спортивному программированию, 24-25 марта 2006 года
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1439. Поединок с И-Так-Понятно-Кем