Little Marica is making up a ~~nonsensical~~ unusual fairy tale and is telling it to her grandfather
who keeps interrupting her and asking her ~~stupid~~ intriguing questions.

In Marica's fairy tale, children, denoted with numbers from to by their age (from the youngest denoted with , to the oldest denoted with ), embarked on a train ride. The train leaves from station and stops in order at stations to infinity.

Each of the following Marica's statements is of the form: "**At stop , child got out**",
where the order of these statements is completely arbitrary. In other words, it does not
depend on the station order. Her grandfather sometimes asks a question of the form:
"**Based on the statements so far, of the children denoted with a number greater than
or equal to , who is the youngest child that rode for or fewer stops?**" If at the
moment the grandfather asks the question it hasn't been said so far that a child is getting off
the train, we assume that the child is riding for an infinite amount of stops.

Marica must give a correct answer to each of her grandfather's questions, otherwise the grandfather will get mad and go to sleep. The answer must be correct at the moment when the grandfather asks the question, while it can change later given Marica's new statements, but that doesn't matter. Write a program that tracks Marica's statements and answers her grandfather's questions.

#### Input Specification

The first line of input contains the positive integers and , the number of children and the number of statements. Each of the following lines describes:

- either Marica's statement of the form
`M`

, where`M`

denotes Marica, and and are positive integers from the task, - or her grandfather's question of the form
`D`

, where`D`

denotes the grandfather, and and are positive integers from the task.

All of Marica's statements correspond to different children and at least one line in the input is her grandfather's question.

#### Output Specification

For each grandfather's question, output the number of the required child in its own line. If no
such child exists, output `-1`

.

#### Sample Input 1

```
3 4
M 10 3
M 5 1
D 20 2
D 5 1
```

#### Sample Output 1

```
3
1
```

#### Sample Input 2

```
10 10
M 20 10
D 1 9
M 2 3
D 17 10
M 20 2
D 8 2
M 40 1
D 25 2
M 33 9
D 37 9
```

#### Sample Output 2

```
-1
-1
3
2
9
```

## Comments

The time limit for this problem has been raised by 0.5 seconds due to the official solution not passing, although the problem statement states the time limit for this problem is 1 second.

dmoj judges too slow :^(