문제

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

• 빈 문자열 은 올바른 괄호 문자열입니다.
• 가 올바른 괄호 문자열이라면, 를 괄호로 둘러싼 또한 올바른 괄호 문자열입니다.
• 와 가 올바른 괄호 문자열이라면, 와 를 붙인 또한 올바른 괄호 문자열입니다.

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

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

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

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

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

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

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

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

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

입력

첫 번째 줄에 수행해야 하는 동작의 수 가 주어집니다. ()

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

출력

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

서브태스크

노트

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