Deda

Source: COCI

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ children whose ages are exactly $1,2,\ldots,N$. A train starts at station $0$ and then visits stations $1,2,3,\ldots$.

The story is told in arbitrary order. There are $Q$ lines, each of one of the following forms:

• M X A: the child aged $A$ gets off at station $X$.
• D Y B: among children aged at least $B$, find the youngest child which, according to all statements known so far, gets off no later than station $Y$.

If no M statement has been given for a child yet, that child is considered to get off at infinity. Each child appears in at most one M statement.

Input

The first line contains $N,Q$.

Each of the next $Q$ lines is M X A or D Y B.

Common limits: $1\le X,Y\le10^9$, $1\le A,B\le N$. There is at least one D query.

Output

For every D query, print the required age, or -1 if no such child exists.

Subtasks

• Subtask 1 — 20%: $2\le N,Q\le50$.
• Subtask 2 — 30%: $2\le N,Q\le5000$.
• Subtask 3 — 50%: $2\le N,Q\le2\cdot10^5$.

Examples

Input

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

Output

3
1

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.