В базовой инфраструктуре проектируют новое хранилище основанное на стеках. Говорят, это будущее! Пока она поддерживает всего 3 операции:

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

Вам необходимо реализовать подсистему поиска - написать программу, которая выводит число на запросы второго типа.

Формат входных данных

В первой строке даны числа n (1 ≤ n ≤ 10⁵) — число стеков, и m (1 ≤ m ≤ 10⁵) — число запросов.

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

Формат выходных данных

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

Пример