22159번 - Текстовый редактор 다국어

Маленький Иван недавно решил написать свой собственный текстовый редактор. Этот текстовый редактор он собирается использовать для написания сложных программ, поэтому ему очень важна функция выделения парных скобок.

На ранней стадии текстовый редактор должен поддерживать всего одну операцию — изменение символа на позиции i. При этом редактор не разрешает иметь текст длиной более n символов. Каждый раз, когда новый символ является открывающей или закрывающей круглой скобкой, редактор должен подсвечивать парную ей скобку, если таковая имеется.

Определим понятие парной скобки. Пусть на позиции i в тексте располагается открывающая скобка. Тогда парной к ней будет закрывающая скобка на позиции j, для которой верны следующие свойства:

• i < j;
• если рассмотреть текст с позиции i до позиции j включительно и удалить из него все символы, не являющиеся круглыми скобками, то получится правильная скобочная последовательность;
• j минимально.

Аналогичным образом определяется парная скобка для закрывающей скобки.

К сожалению, Ивану не удалось реализовать желаемую функциональность. Ваша задача состоит в том, чтобы по заданным операциям, для каждой операции изменения символа на круглую скобку находить к ней парную.

Первая строка содержит целые числа n (1 ≤ n ≤ 100000) — максимальная длина текста, и m (1 ≤ m ≤ 100000) — число операций модификации символа.

Далее, в m строках описаны изменения операции изменения символа в виде целого числа i — позиции, в которой изменяется символ, и нового символа c (1 ≤ i ≤ n, c является строчной буквой латинского алфавита, открывающей или закрывающей круглой скобкой). Изначально считается, что текст состоит из n строчных латинских букв “a”.

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