“括号字符串”是指由两种字符组成的字符串：左括号 "(" 和右括号 ")"。在所有括号字符串中，我们区分出合法括号序列。合法括号序列是指其中的括号可以两两配对，并满足以下条件的括号字符串：

• 每个配对由一个左括号和（在字符串中位置更靠后的）一个右括号组成。
• 对于每个配对，夹在这两个括号之间的括号字符串片段中，左括号的数量与右括号的数量相等。

我们可以对括号字符串执行以下操作：

• 修改：将字符串中的第 $i$ 个括号修改为相反的括号（即 "(" 变成 ")"，")" 变成 "("）。
• 查询：检查当前的括号字符串是否为合法括号序列。

给定一个初始括号字符串，依次对其执行一系列修改或查询操作。

编写一个程序：

• 从标准输入读取括号字符串以及依次对该字符串执行的操作序列。
• 对于每个查询操作，判断当前的括号字符串是否为合法括号序列。
• 将结果输出到标准输出。

输入格式

输入第一行包含一个整数 $n$（$1 \le n \le 30\,000$），表示括号字符串的长度。

第二行包含 $n$ 个括号，中间没有空格。

第三行包含一个整数 $m$（$1 \le m \le 1\,000\,000$），表示对括号字符串执行的操作次数。

接下来的 $m$ 行，每行包含一个整数。如果在第 $k + 3$ 行（对于 $1 \le k \le m$）的数字是 $0$，则表示第 $k$ 次操作是查询操作。如果是一个满足 $1 \le p \le n$ 的整数 $p$，则表示该操作是将第 $p$ 个括号修改为相反的括号。

输出格式

你的程序应该在标准输出的连续行中输出每次查询操作的结果。如果当前的括号字符串是合法括号序列，则输出 TAK；否则输出 NIE。（输出的行数应与输入中的查询操作次数相同。）

样例

输入样例 1

4
() ((
4
4
0
2
0

输出样例 1

TAK
NIE