29102번 - Стеки 다국어

문제

В давние времена, когда Магнето и Чарльз Ксавьер работали в одной команде, они любили играть в одну игру. Правила победы, очередность ходов и всё остальное их не интересовало --- кто убедительнее докажет, что сейчас его ход, тот и ходит. Определение победителя тоже выливалось в философский спор, не имеющий отношения к игре, и переходящий к вопросу о роли мутантов в обществе.

Нас же интересует сам процесс игры. У игроков есть $n$ изначально пустых стеков. Каждый игрок может сделать один из трёх ходов:

• A l r x --- положить на вершину каждого из стеков с $l$ по $r$ число $x$;
• G x --- спросить у соперника число, лежащее на вершине $x$-го стека;
• R i --- отменить $i$-й по порядку запрос добавления числа на стеки: удалить соответствующее число из каждого стека.

В один день Чарльз заметил, что Магнето стал отвечать слишком быстро. После непродолжительного наблюдения, он заметил, что хитрый Магнето написал программу, которая делает всё за него. Чарльзу это, конечно, не понравилось, но он не стал обвинять соперника в мошенничестве: это бы ещё больше увеличило напряжение в их отношениях. Вместо этого он решил сам автоматизировать процесс, чтобы не отставать от своего извечного соперника.

Напишите программу, которая сумеет играть в такую игру не хуже, чем Ксавьер и Магнето.

입력

В первой строке даны числа $n$ (1ドル \le n \le 10^5$) --- число стеков, и $m$ (1ドル \le m \le 10^5$) --- число запросов.

В следующих $m$ строках даны запросы в формате, описанном в условии. Гарантируется, что все номера стеков лежат в интервале от 1ドル$ до $n,ドル а числа, которые кладутся на стек, удовлетворяют ограничению (1ドル \le x \le 10^9$). Для любого запроса на отмену добавления гарантируется, что соответствующий запрос добавления уже был исполнен, и ни один запрос не отменяется дважды.

출력

Для каждого запроса второго типа выведите одно число --- число, находящееся на вершине соответствующего стека, или -1, если соответствующий стек пуст.

제한

힌트