[COCI2017-2018#1] Deda

### 题面描述 小马里卡正在创作一个奇妙的童话故事。她一边编故事，一边讲给她的爷爷听。爷爷可高兴了，于是问了她一些有趣的问题。 在小马里卡的故事中，有 $N$ 个年龄分别为 $1$~$N$ 岁的孩子（最小的为 $1$ 岁，最大的为 $N$ 岁）。有一天，她们一起乘火车出去旅行。铁路线上有好多个车站，分别以 $0, 1, 2, 3 \dots$ 编号。其中第 $0$ 站为始发站，火车每到一个车站都会停下来逗留一段时间。每个孩子都可以在选择自己喜欢的车站下车。 小马里卡喜欢这样讲述她的故事：“在第 $X$ 站，年龄为 $A$ 岁的孩子下车了。”不过小马里卡的习惯非常不好，她讲述故事的顺序是完全随机的。换句话说，$X$ 是不单调的。爷爷知道小马里卡的坏习惯，所以他喜欢时不时问一些有趣的问题来找小马里的麻烦。问题是这样的：“年龄大于等于 $B$ 且在第 $Y$ 站（包含第 $Y$ 站）以前下车的最年轻的小孩是多大？” 小马里卡必须正确回答爷爷的问题，否则爷爷会因生气而睡觉。值得注意的是，小马里卡的答案必须在当时是正确的。虽然小马里卡在随后的讲述中可能会改变问题的答案，但这都是无关紧要的。 小马里卡对自己的坏习惯十分无奈。由于故事的顺序过于杂乱，小马里卡根本无法正确回答爷爷的问题。于是她找到了聪明的你。请帮小马里卡编写一个程序，动态追踪她的讲述，并回答爷爷的问题。 ### 输入格式 输入的第一行包含两个正整数 $N,Q\ (2 \le N,Q \le 2 \times 10^{5})$，分别代表孩子的数量和语句的数量。 接下来 $Q$ 行，每行一个语句。语句的格式为 `M X A` 或 `D Y B`，分别代表小马里卡的讲述和爷爷的问题。其中 `M`、`D` 为大写字母，$X$、$Y$、$A$、$B$ $(1 \le X,Y \le 10^{9},1 \le A,B \le N)$ 分别为一个正整数。其意义请见【题面描述】。题目中保证至少有一个 `D`。 ### 输出格式 对于每一个问题 `D` 输出一个答案。答案为一个整数。如果爷爷的问题无解，请输出 `-1`。

Little Marica is making up a ~~nonsensical~~ unusual fairy tale and is telling to her grandfather who keeps interrupting her and asking her ~~stupid~~ intriguing questions. In Marica’s fairy tale, $N$ children, denoted with numbers from $1$ to $N$ by their age (from the youngest denoted with $1$, to the oldest denoted with $N$), embarked on a train ride. The train leaves from the station $0$ and stops in order at stations $1, 2, 3 \dots$ to infinity. Each of the following Marica’s statements is of the form: “$At\ stop\ X, child\ A\ 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: “$\textit{ Based on the statements so far, of the children denoted with a number greater than or equal}\allowbreak\textit{ to B, who is the youngest child that rode for Y or less 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 in 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.

The first line of input contains the positive integers $N$ and $Q$ $(2 \le N, Q \le 2 \times 10^{5})$, the number of children and the number of statements. Each of the following $Q$ lines describes: - either Marica’s statement of 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)$ from the task, - or her grandfather’s question of 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)$ 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.

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

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

3
1

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

-1
-1
3
2
9