괄호

괄호 문자열은 여는 괄호 ( 와 닫는 괄호 ) 두 종류의 문자로만 이루어진 문자열입니다. 괄호 문자열 가운데, 다음 조건을 만족하도록 괄호들을 짝지을 수 있는 것을 올바른 괄호 문자열이라고 합니다.

• 각 짝은 여는 괄호 하나와, 그보다 뒤에 나오는 닫는 괄호 하나로 이루어진다.
• 각 짝에 대해, 그 짝을 이루는 두 괄호 사이에 있는 부분 문자열은 여는 괄호와 닫는 괄호의 개수가 서로 같다.

괄호 문자열에는 다음 두 가지 연산을 적용할 수 있습니다.

• 뒤집기: i번째 괄호를 반대 방향의 괄호로 바꿉니다(( ↔ )).
• 검사: 현재 괄호 문자열이 올바른 괄호 문자열인지 확인합니다.

어떤 괄호 문자열에 대해 뒤집기 또는 검사 연산이 차례대로 주어집니다. 표준 입력으로 괄호 문자열과 그에 대해 순서대로 수행할 연산들을 읽어, 각 검사 연산마다 그 시점의 괄호 문자열이 올바른 괄호 문자열인지 판정하여 그 결과를 표준 출력에 출력하는 프로그램을 작성하세요.

첫째 줄에 괄호 문자열의 길이를 나타내는 정수 n ($1 \le n \le 30000$)이 주어집니다. 둘째 줄에는 n개의 괄호가 사이에 공백 없이 주어집니다. 셋째 줄에는 수행할 연산의 개수를 나타내는 정수 m ($1 \le m \le 10^6$)이 주어집니다. 이어지는 m개의 줄에는 각각 정수가 하나씩 주어집니다. 그 값이 0이면 그 연산은 검사 연산입니다. 값이 $1 \le p \le n$을 만족하는 정수 p이면, 그 연산은 p번째 괄호를 반대 방향으로 뒤집는 연산입니다.

각 검사 연산의 결과를 순서대로 한 줄에 하나씩 출력합니다. 그 시점의 괄호 문자열이 올바른 괄호 문자열이면 TAK을, 그렇지 않으면 NIE를 출력합니다. (출력되는 줄의 수는 입력으로 주어진 검사 연산의 개수와 같습니다.)