32966번 - 괄호 문자열 편집기 서브태스크

올바른 괄호 문자열은 다음과 같이 정의됩니다.

• 빈 문자열 $\varnothing$은 올바른 괄호 문자열입니다.
• $A$가 올바른 괄호 문자열이라면, $A$를 괄호로 둘러싼 $(A)$ 또한 올바른 괄호 문자열입니다.
• $A$와 $B$가 올바른 괄호 문자열이라면, $A$와 $B$를 붙인 $AB$ 또한 올바른 괄호 문자열입니다.

여러분은 이 문제에서 텍스트 편집기를 관리하면서 현재 편집기의 텍스트가 올바른 괄호 문자열인지의 여부를 실시간으로 판정해야 합니다. 구현해야 하는 텍스트 편집기는 다음과 같은 명세를 따릅니다.

초기에 편집기의 텍스트는 빈 문자열 $\varnothing$입니다. 이 편집기에는 하나의 커서가 있습니다. 편집기의 텍스트가 $S$이고 커서의 위치가 $j$일 때, 편집기가 지원해야 하는 동작은 아래와 같이 정의됩니다.

• (: $S$의 $j$번째 문자와 $j+1$번째 문자 사이에 문자 (를 삽입하고 커서의 위치를 $1$만큼 뒤로 옮깁니다. $j=0$인 경우 문자열의 맨 앞에, $j=|S|$인 경우 끝에 문자를 삽입합니다.
• ): $S$의 $j$번째 문자와 $j+1$번째 문자 사이에 문자 )를 삽입하고 커서의 위치를 $1$만큼 뒤로 옮깁니다. $j=0$인 경우 문자열의 맨 앞에, $j=|S|$인 경우 끝에 문자를 삽입합니다.
• <: 커서의 위치를 $1$만큼 앞으로 옮깁니다. 단, $j=0$인 경우 커서는 움직이지 않습니다.
• >: 커서의 위치를 $1$만큼 뒤로 옮깁니다. 단, $j=|S|$인 경우 커서는 움직이지 않습니다.
• X: $S$의 $j$번째 문자를 삭제하고 커서의 위치를 $1$만큼 앞으로 옮깁니다. $j=0$인 경우에는 아무것도 하지 않습니다.

편집기가 지원하는 동작의 정의에 의해 매 순간 $0 \le j \le |S|$가 성립하며, 초기에 $j$의 값은 $0$입니다.

각 동작이 시행된 후에 여러분은 편집기의 텍스트 $S$가 올바른 괄호 문자열인지 기록해야 합니다. 편집기에는 이를 위한 변수 $C$가 있으며, 초기에 그 값은 $0$입니다.

각 동작이 시행된 후 여러분은 $C$를 다음과 같이 변경해야 합니다.

• $i$번째 동작을 수행한 후 $S$가 올바른 괄호 문자열이라면 $C$의 값을 $C \oplus i$으로 변경합니다.$^\dagger$

여러분은 명세에 따라 편집기를 구현한 뒤, $Q$개의 동작을 수행하여 마지막에 얻은 $C$의 값을 출력하는 프로그램을 작성해야 합니다.

$^\dagger$ 두 정수 $x$와 $y$가 주어질 때 $x \oplus y$는 두 정수의 비트 XOR을 의미하며, 대부분 프로그래밍 언어에서 (x ^ y)와 같이 사용할 수 있습니다.

첫 번째 줄에 수행해야 하는 동작의 수 $Q$가 주어집니다. ($1 \le Q \le 10\, 000\, 000$)

두 번째 줄에 수행해야 하는 동작을 모두 순서대로 늘어놓은 길이 $Q$의 문자열 $P$가 주어집니다.

$Q$개의 동작을 모두 수행한 뒤 마지막에 얻은 $C$의 값을 한 줄에 출력합니다.

예제 입출력에서 각 동작을 수행한 후 텍스트와 커서, 변수 $C$의 상태는 아래와 같습니다.