小 Marica 正在编一个荒诞而奇特的神话故事，并讲给她的爷爷听。她的爷爷总是打断她，并问她一些愚蠢但有趣的问题。

在 Marica 的神话故事中，有 $N$ 个孩子，按年龄从小到大用 $1$ 到 $N$ 的数字表示（最年轻的用 $1$ 表示，最年长的用 $N$ 表示），他们乘上了一辆火车。火车从 $0$ 号车站出发，并依次在 $1, 2, 3 \dots$ 号车站停靠，直到无穷远。

Marica 随后的每条陈述都具有以下形式：“在第 $X$ 站，孩子 $A$ 下车了”。这些陈述的顺序是完全随机的。换句话说，它们不依赖于车站的顺序。她的爷爷有时会提出如下形式的问题：“根据目前的陈述，在编号大于或等于 $B$ 的孩子中，乘车不超过 $Y$ 站的最年轻（即编号最小）的孩子是谁？”如果在爷爷提问时，还没有提到某个孩子下车，我们假设该孩子会乘车无限站。

Marica 必须对爷爷的每个问题给出正确的回答，否则爷爷会生气并去睡觉。回答必须在爷爷提问的时刻是正确的，虽然之后由于 Marica 的新陈述，答案可能会发生变化，但这并不重要。请编写一个程序，记录 Marica 的陈述并回答她爷爷的问题。

输入格式

输入的第一行包含两个正整数 $N$ 和 $Q$（$2 \le N, Q \le 200\,000$），分别表示孩子的数量和陈述/提问的总数。

接下来的 $Q$ 行中，每行描述以下内容之一：

• 或者是 Marica 的陈述，格式为 M X A，其中 M 表示 Marica，$X$ 和 $A$ 是正整数（$1 \le X \le 1\,000\,000\,000$，$1 \le A \le N$）；
• 或者是她爷爷的提问，格式为 D Y B，其中 D 表示爷爷，$Y$ 和 $B$ 是正整数（$1 \le Y \le 1\,000\,000\,000$，$1 \le B \le N$）。

Marica 的所有陈述都对应不同的孩子，且输入中至少有一行是爷爷的提问。

输出格式

对于爷爷的每个提问，在单独的一行中输出满足条件的孩子编号。如果不存在这样的孩子，则输出 -1。

样例

输入样例 1

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

输出样例 1

3
1

输入样例 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

输出样例 2

-1
-1
3
2
9