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 ≤ 10⁹) and a number M (1 ≤ M ≤ 10⁵). Each of the subsequent M lines has the following format:
<letter> <number>
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 10⁴ rooms will be destroyed during the battle.

The output must contain for each line
L <number>
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.