Problem Description

Little Marica is creating an unusual fairy tale and narrating it to her grandfather, who frequently interrupts with intriguing questions.

In Marica's tale, there are $N$ children, each identified by their age ranging from 1 to $N$ (from the youngest to the oldest). These children embark on a train journey. The train departs from station 0 and stops sequentially at stations 1, 2, 3, and so on indefinitely.

Marica describes her story with statements like: "At stop $X$, child $A$ got off." However, the order of these statements is completely random, not following the sequence of stops. Her grandfather occasionally asks questions like: "Among the children aged $B$ or older, who is the youngest child who got off at or before stop $Y$?" If it hasn't been mentioned that a child got off the train, it is assumed they rode indefinitely.

Marica must answer her grandfather's questions correctly at the time they are asked, though her answers might change with subsequent statements, which is irrelevant. Write a program to track Marica's statements and respond to her grandfather's questions.

Input Format

The first line contains two positive integers $N$ and $Q$ $(2 \le N, Q \le 2 \times 10^{5})$, representing the number of children and the number of statements, respectively.

Each of the following $Q$ lines describes either:
- Marica's statement in the form M X A, where $M$ denotes Marica, and $X$ and $A$ are positive integers $(1 \le X \le 10^{9}, 1 \le A \le N)$,
- or her grandfather's question in the form D Y B, where $D$ denotes the grandfather, and $Y$ and $B$ are positive integers $(1 \le Y \le 10^{9}, 1 \le B \le N)$.

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

Output Format

For each of her grandfather's questions, output the number of the required child on a new line. If no such child exists, output -1.

Sample Input and Output

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

见题面 Input 部分

见题面 Output 部分