«Лабораторная C#»,
Программирование, си-шарп в Санкт-Петербурге

Задача на строки В не столь далекие времена, когда Ольга Павловна и Ольга Владимировна учились на математическом факультете, они любили играть в одну игру. Правила победы, очередность ходов и всё остальное их не интересовало — кто убедительнее докажет, что сейчас его ход, тот и ходит. Определение победителя тоже выливалось в философский спор, не имеющий отношения к игре, и переходящий к вопросу о роли Информатики в обществе. Нас же интересует сам процесс игры. У игроков есть n изначально пустых стеков. Каждый игрок может сделать один из трёх ходов: A l r x — положить на вершину каждого из стеков с l по r число x; G x — спросить у соперника число, лежащее на вершине x-го стека; R i — отменить i-й по порядку запрос добавления числа на стеки: удалить соответствующее число из каждого стека. В один день Ольга Павловна заметила, что Ольга Владимировна стала отвечать слишком быстро. После непродолжительного наблюдения, она заметила, что хитрая Ольга Владимировна написала программу, которая делает всё за неё. Ольге Павловне это, конечно, она решила сама автоматизировать процесс, чтобы не отставать от своего соперника. Напишите программу, которая сумеет играть в такую игру не хуже, чем Ольга Павловна и Ольга Владимировна. Формат ввода В первой строке даны числа n (1 ≤ n ≤ 105) — число стеков, и m (1 ≤ m ≤ 105) — число запросов. В следующих m строках даны запросы в формате, описанном в условии. Гарантируется, что все номера стеков лежат в интервале от 1 до n, а числа, которые кладутся на стек, удовлетворяют ограничению (1 ≤ x ≤ 109). Для любого запроса на отмену добавления гарантируется, что соответствующий запрос добавления уже был исполнен, и ни один запрос не отменяется дважды. Формат вывода Для каждого запроса второго типа выведите одно число — число, находящееся на вершине соответствующего стека, или -1, если соответствующий стек пуст. Пример Ввод Вывод 3 7 A 1 3 5 A 2 3 3 G 1 G 2 R 1 G 1 G 2 5 3 -1 3