텍스트 편집기

어린 이반은 최근 자신만의 텍스트 편집기를 만들기로 했다. 이 편집기로 복잡한 프로그램을 작성할 계획이므로 짝이 맞는 괄호를 강조 표시하는 기능이 매우 중요하다.

초기 단계에서 텍스트 편집기는 단 하나의 연산만 지원하면 된다. 바로 i번 위치의 문자를 바꾸는 것이다. 이때 편집기는 텍스트 길이가 n자를 넘도록 허용하지 않는다. 새로 입력한 문자가 여는 괄호나 닫는 괄호일 때마다, 편집기는 짝이 되는 괄호가 있다면 그 괄호를 강조 표시해야 한다.

짝이 되는 괄호를 정의하자. 텍스트의 i번 위치에 여는 괄호가 있다고 하자. 이때 짝이 되는 괄호는 다음 조건을 만족하는 j번 위치의 닫는 괄호이다.

• i < j이다.
• i번 위치부터 j번 위치까지의 텍스트에서 괄호가 아닌 문자를 모두 지우면 올바른 괄호열이 된다.
• j는 최소이다.

닫는 괄호의 짝이 되는 괄호도 같은 방식으로 정의한다.

아쉽게도 이반은 원하는 기능을 구현하지 못했다. 여러분이 해야 할 일은 주어진 연산들에 대해, 문자가 괄호로 바뀌는 각 연산마다 그 괄호의 짝을 찾는 것이다.

첫째 줄에 정수 n (1 ≤ n ≤ 100000)과 m (1 ≤ m ≤ 100000)이 주어진다. n은 텍스트의 최대 길이이고, m은 문자를 바꾸는 연산의 수이다.

다음 m개 줄에는 문자를 바꾸는 연산이 정수 i와 새 문자 c로 주어진다. i는 문자가 바뀌는 위치이고, c는 라틴 소문자, 여는 괄호, 닫는 괄호 중 하나이다. (1 ≤ i ≤ n)

처음 텍스트는 라틴 소문자 “a” n개로 이루어져 있다.

문자가 괄호로 바뀌는 연산마다 짝이 되는 괄호의 위치를 한 줄에 하나씩 출력한다. 짝이 되는 괄호가 없으면 그 줄에 -1을 출력한다.