괄호 문자열 편집기

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

• 빈 문자열 $\varnothing$은 올바른 괄호 문자열이다.
• $A$가 올바른 괄호 문자열이면, $A$를 괄호로 둘러싼 $(A)$도 올바른 괄호 문자열이다.
• $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이다.

$i$번째 동작을 수행한 뒤 $S$가 올바른 괄호 문자열이면, $C$의 값을 $C \oplus i$로 바꾼다. 여기서 $\oplus$는 비트 XOR이다.

명세대로 편집기를 구현한 뒤, $Q$개의 동작을 모두 수행하고 마지막에 얻은 $C$의 값을 출력하는 프로그램을 작성하라.

첫 번째 줄에 수행할 동작의 수 $Q$가 주어진다. ($1 \le Q \le 10\,000\,000$)

두 번째 줄에 수행할 동작을 순서대로 늘어놓은 길이 $Q$의 문자열 $P$가 주어진다.

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

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