A bracket sequence is a word consisting of two types of characters: opening brackets, "(", and closing brackets, ")". Among all bracket sequences, we distinguish correct bracket expressions. These are bracket sequences in which the brackets can be paired such that:

• each pair consists of an opening bracket and a closing bracket (which appears later in the bracket sequence),
• for each pair, the fragment of the bracket sequence contained between the brackets of this pair contains an equal number of opening and closing brackets.

The following operations can be performed on a bracket sequence:

• modification, which changes the $i$-th bracket in the word to its opposite,
• check, which verifies whether the bracket sequence is a correct bracket expression.

A sequence of modification or check operations is performed on a given bracket sequence.

Write a program that:

• reads the bracket sequence and the sequence of operations performed on it from standard input,
• for each check operation (occurring in the input sequence of operations), determines whether the current bracket sequence is a correct bracket expression,
• prints the result to standard output.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 30\,000$) representing the length of the bracket sequence. The second line contains $n$ brackets with no spaces between them. The third line contains a single integer $m$ ($1 \le m \le 1\,000\,000$) representing the number of operations performed on the bracket sequence. Each of the following $m$ lines contains a single integer. If the $(k + 3)$-th line (for $1 \le k \le m$) contains the number 0, it means that the $k$-th operation performed on the bracket sequence is a check operation. If it is an integer $p$ such that $1 \le p \le n$, it means that the operation is a modification of the $p$-th bracket to its opposite.

Output

Your program should print the results of the successive check operations in consecutive lines (of standard output). If the current bracket sequence is a correct bracket expression, print TAK, otherwise print NIE. (The output should contain as many lines as there were check operations in the input.)

Examples

Input 1

4
() ((
4
4
0
2
0

Output 1

TAK
NIE