5022 - [COCI 2017-2018 #1] Deda

小马里卡正在创作一个奇妙的童话故事。她一边编故事，一边讲给她的爷爷听。爷爷可高兴了，于是问了她一些有趣的问题。

在小马里卡的故事中，有 N 个年龄分别为 1\sim N 岁的孩子（最小的为 1 岁，最大的为 N 岁）。有一天，她们一起乘火车出去旅行。铁路线上有好多个车站，分别以 0, 1, 2, 3 \dots 编号。其中第 0 站为始发站，火车每到一个车站都会停下来逗留一段时间。每个孩子都可以在选择自己喜欢的车站下车。

小马里卡喜欢这样讲述她的故事：“在第 X 站，年龄为 A 岁的孩子下车了。”不过小马里卡的习惯非常不好，她讲述故事的顺序是完全随机的。换句话说，X 是不单调的。爷爷知道小马里卡的坏习惯，所以他喜欢时不时问一些有趣的问题来找小马里的麻烦。问题是这样的：“年龄大于等于 B 且在第 Y 站（包含第 Y 站）以前下车的最年轻的小孩是多大？”

小马里卡必须正确回答爷爷的问题，否则爷爷会因生气而睡觉。值得注意的是，小马里卡的答案必须在当时是正确的。虽然小马里卡在随后的讲述中可能会改变问题的答案，但这都是无关紧要的。

小马里卡对自己的坏习惯十分无奈。由于故事的顺序过于杂乱，小马里卡根本无法正确回答爷爷的问题。于是她找到了聪明的你。请帮小马里卡编写一个程序，动态追踪她的讲述，并回答爷爷的问题。

输入的第一行包含两个正整数 N,Q，分别代表孩子的数量和语句的数量。

接下来 Q 行，每行一个语句。语句的格式为 M X A 或 D Y B，分别代表小马里卡的讲述和爷爷的问题。其中 M D 为大写字母，X,Y,A,B 分别为一个正整数。数据中保证至少有一个 D。

对于每一个问题 D 输出一个答案。答案为一个整数。如果爷爷的问题无解，请输出 -1。

对于 100\% 的数据，2 \le N,Q \le 2 \times 10^5,1 \le X,Y \le 10^9,1 \le A,B \le N。