Bajtazar 最近对他的姓氏起源产生了兴趣。在他的家族中，有一个习俗：如果父母的姓氏分别为 $u$ 和 $w$，那么孩子姓氏的组成方式要么是 $uw$，要么是 $wu$，具体取决于父母的偏好。
Bajtazar 从抽屉里翻出了档案记录，找到了 $n$ 代以前祖先的姓氏。我们称这些祖先为“原始祖先”。令他惊讶的是，当时的姓氏仅由一个英文字母组成。这些祖先共有 $2^n$ 个，因为 Bajtazar 有 2 位父母、4 位祖父母、8 位曾祖父母，以此类推。我们将这些祖先编号为 $1$ 到 $2^n$。祖先 $1$ 与祖先 $2$ 结合，祖先 $3$ 与祖先 $4$ 结合，以此类推。每一对结合产生一个孩子；我们将这些孩子同样编号为 $1$ 到 $2^{n-1}$，即祖先 $1$ 和 $2$ 的孩子编号为 $1$，以此类推。随后重复整个过程，直到最终得到 Bajtazar 这一代，此时只剩下他一个人。
因此，Bajtazar 的姓氏长度为 $2^n$，但他不清楚这个姓氏是如何形成的。毕竟，祖先们可以自由选择在孩子的姓氏中，哪一个父母的姓氏在前。正因如此，Bajtazar 开始怀疑档案记录是否有误，并请求你的帮助。
整个情况是动态的，Bajtazar 会对档案记录以及（这可能有些不同寻常）他自己的姓氏进行修改。你的任务是回答 Bajtazar：在初始状态以及每次 $q$ 次修改后，他的当前姓氏是否可能由档案中当前的祖先姓氏根据上述规则组合而成。第 $i$ 次事件属于以下两种类型之一：
- Bajtazar 将他姓氏的第 $k_i$ 个字母修改为 $b_i$。
- 原始祖先 $k_i$ 的姓氏实际上是 $b_i$（$b_i$ 为一个字母）。
输入格式
第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 20$, $0 \le q \le 1\,000\,000$)。 第二行包含一个长度为 $2^n$ 的字符串，描述 Bajtazar 的姓氏。 第三行包含一个长度为 $2^n$ 的字符串，其中第 $i$ 个字母表示原始祖先 $i$ 的姓氏。 两个字符串均仅由小写英文字母（a, b, ..., z）组成，且不含任何空格。
接下来的 $q$ 行描述后续事件。第 $i$ 次事件包含两个整数 $t_i, k_i$ 和一个小写英文字母 $b_i$ ($1 \le t_i \le 2$, $1 \le k_i \le 2^n$)。如果 $t_i = 1$，则表示将 Bajtazar 姓氏的第 $k_i$ 个字母修改为 $b_i$。如果 $t_i = 2$，则表示将原始祖先 $k_i$ 的姓氏修改为 $b_i$。
输出格式
程序应输出 $q+1$ 行。第一行应为所有事件发生前的回答，后续 $q$ 行应为每次事件发生后的回答。
如果当前的姓氏可以由当前的档案记录根据姓氏生成规则产生，则输出 TAK，否则输出 NIE。
样例
输入格式 1
2 4 abcd cadb 1 2 c 2 4 c 1 1 d 1 4 a
输出格式 1
NIE NIE TAK NIE TAK
说明
示例解释：以下是 Bajtazar 在所有事件发生前及每次事件后的记录：
- Bajtazar 的姓氏为
abcd，祖先姓氏依次为c,a,d,b。回答 NIE。 - Bajtazar 的姓氏为
accd，祖先姓氏依次为c,a,d,b。回答 NIE。 - Bajtazar 的姓氏为
accd，祖先姓氏依次为c,a,d,c。回答 TAK。Bajtazar 的父母姓氏分别为ac和cd；见下图。
- Bajtazar 的姓氏为
dccd，祖先姓氏依次为c,a,d,c。回答 NIE。 - Bajtazar 的姓氏为
dcca，祖先姓氏依次为c,a,d,c。回答 TAK。Bajtazar 的父母姓氏分别为ca和dc。