괄호 뒤집기

( 와 ) 로만 이루어진 문자열이 다음 조건 가운데 하나를 만족하면 균형 잡힌 문자열이라고 한다.

• () 는 균형 잡힌 문자열이다.
• 균형 잡힌 두 문자열을 이어 붙인 문자열도 균형 잡힌 문자열이다.
• 문자열 $s$ 가 균형 잡혀 있으면 (, $s$, ) 를 이 순서로 이어 붙인 문자열도 균형 잡혀 있다.

이 조건은 ( 의 개수와 ) 의 개수가 같다는 조건보다 강하다. 예를 들어 ())(() 는 두 괄호의 개수가 같지만 균형 잡힌 문자열이 아니다.

우주 방사선이 괄호 하나의 방향을 뒤집는 가혹한 환경에서 문자열을 계속 균형 잡힌 상태로 유지하는 것이 목표다.

처음에 균형 잡힌 문자열을 받는다. 괄호 하나의 방향이 뒤집힐 때마다 바뀐 문자의 위치를 알려 준다. 그러면 그 위치의 괄호를 뒤집었을 때 문자열 전체가 다시 균형 잡힌 상태가 되는 위치 가운데 가장 왼쪽 위치를 계산해 출력한다. 프로그램이 알려 준 괄호를 뒤집어 균형을 되찾고 나면 다음 우주 방사선이 또 다른 괄호를 뒤집고, 같은 과정이 여러 번 반복된다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

N Q
s
q1
.
.
.
qQ

첫 줄에 두 정수 $N$ 과 $Q$ 가 주어진다 ($2 \le N \le 300000$, $1 \le Q \le 150000$). 둘째 줄에 길이가 $N$ 인 균형 잡힌 괄호 문자열 $s$ 가 주어진다. 이어지는 $Q$ 개의 줄에는 각각 정수 $q_i$ 가 주어지며 ($1 \le q_i \le N$), $q_i$ 번째 괄호의 방향이 뒤집혔다는 뜻이다.

각 사건 $q_i$ 마다 균형 잡힌 상태로 되돌리기 위해 뒤집어야 하는 괄호의 위치 가운데 가장 왼쪽 위치를 한 줄에 하나씩 출력한다. 그런 위치는 항상 존재한다.

각 사건 $q_i$ 는 직전 사건 $q_{i-1}$ 과 그에 대한 수정까지 모두 반영된 문자열에 적용된다.

첫 번째 예제의 처음 상태는 ((())) 다. 4번째 괄호가 뒤집혀 문자열은 (((()) 가 된다. 균형을 되찾으려면 2번째 괄호를 뒤집어 ()(()) 를 만들어야 한다. 다음 뒤집기인 3번째 괄호는 이 마지막 상태에 적용되어 ())()) 가 된다. 여기서 다시 2번째 괄호를 바꾸면 (()()) 가 되어 균형이 맞는다.