Rooms of the Ministry of Magic are enchanted with a spell which
enumerates them automatically. The spell works as follows. The
first room created at the Ministry got the number 1. When a
new room is created by magic, a number-plate appears at once
upon the door. The new number is greater by one than the maximal
room number existing at the moment. If a room is not needed anymore,
then it is destroyed and all the room numbers that are greater
than the number of the destroyed room are lessened by one. Thus,
the numeration of the rooms at the Ministry always remains continuous.
Harry Potter found out a list of the numbers of the rooms where
Lord Voldemort's Horcruxes are stored (A Horcrux is a magical artifact that provides for the owner's immortality).
It seems that now it will be easy for Harry to find the Horcruxes
and destroy them. But the task turned out to be more complicated.
Because of his mysterious bond with Harry, Voldemort knew at once
about Harry's discovery, so he transported himself to the Ministry and
started to destroy rooms. This means that numbers of rooms are
changing, so when Harry looks at a room's door, he doesn't know
which number this door had before. But he knows which numbers were on the
doors of the rooms that were destroyed by Voldemort, due to the
mentioned bond between them.
Help Harry to defeat Voldemort. You don't have to fight Harry's
enemy, but you can help him to determine the true numbers of rooms
when he looks at their doors.
The first line contains the number of rooms at the Ministry of
Magic N (1 ≤ N ≤ 109) and a number M (1 ≤ M ≤ 105). Each of the subsequent M lines has the following format:
where <letter> is one of the letters 'D' (Destroy) or 'L' (Look at),
and <number> is the number on the door of the room which is
destroyed or at which Harry looks at the moment. It is guaranteed
that not more than 104 rooms will be destroyed during the battle.
The output must contain for each line
of the input the true number (which it had before the
battle) of the room at which Harry looks.
The numbers must be given one in a line.
Problem Author: Alexander Klepinin, Stanislav Vasilyev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006