Parentheses

A bracket word is a string made up of only two kinds of characters: opening brackets ( and closing brackets ). Among all bracket words we single out the correct bracket expressions: these are the bracket words whose brackets can be matched into pairs so that

• each pair consists of one opening bracket together with one closing bracket that appears later in the word, and
• for every pair, the fragment of the word lying strictly between that pair's two brackets contains equally many opening and closing brackets.

Two operations can be applied to a bracket word:

• flip, which replaces the i-th bracket of the word with the opposite bracket (( ↔ ));
• check, which tests whether the current bracket word is a correct bracket expression.

A sequence of flip and check operations is applied to a bracket word in order. Write a program that reads a bracket word and the sequence of operations from standard input, and for every check operation reports whether the bracket word is a correct bracket expression at that moment.

The first line contains an integer n ($1 \le n \le 30000$), the length of the bracket word. The second line contains the n brackets with no spaces between them. The third line contains an integer m ($1 \le m \le 10^6$), the number of operations. Each of the next m lines contains a single integer. If that integer is 0, the operation is a check. If it is an integer p with $1 \le p \le n$, the operation flips the p-th bracket to the opposite one.

For every check operation, print its result on its own line, in order. Print TAK if the bracket word is a correct bracket expression at that moment, and NIE otherwise. (The number of printed lines equals the number of check operations in the input.)