Bajtazar has recently become interested in the origin of his surname. In his family, it is customary that a child of parents with surnames $u$ and $w$ has the surname $uw$ or $wu$, depending on the parents' preference.
Bajtazar dug through archival records and found the surnames of his ancestors $n$ generations ago. Let us call these ancestors the "original" ones. To his surprise, the surnames at that time consisted of a single lowercase English letter. There were $2^n$ such ancestors, because Bajtazar has two parents, four grandparents, eight great-grandparents, and so on. We number these ancestors from $1$ to $2^n$. Ancestor $1$ was in a relationship with ancestor $2$, ancestor $3$ with ancestor $4$, and so on. Each of these pairs had exactly one child; the children of the ancestors are numbered similarly from $1$ to $2^{n-1}$, meaning the child of ancestors $1$ and $2$ gets number $1$, and so on. We then repeat the entire process in an analogous way until we finally reach Bajtazar's generation, in which there is only him.
Bajtazar's surname is therefore of length $2^n$, but it is not clear to him how it was formed. After all, the ancestors could freely choose which of the surnames would come first in the child's surname. For this reason, Bajtazar began to doubt whether there might be an error in the archival records, and he asked you for help.
The whole situation is dynamic; Bajtazar makes corrections to the archival records and (which may be somewhat unusual) to his own surname. Your task is to answer Bajtazar, at the very beginning and after each of the $q$ events, whether his current surname could have been formed as a result of combining surnames from the archive according to the rules described above. The $i$-th event is of one of the following two types:
- Bajtazar changes the $k_i$-th letter of his surname to $b_i$.
- The original ancestor $k_i$ actually had the surname $b_i$, where $b_i$ is a letter.
Input
The first line of input contains two integers $n$ and $q$ ($1 \le n \le 20$, $0 \le q \le 1\,000\,000$). The next line contains a string of $2^n$ letters describing Bajtazar's surname. The next line contains a string of $2^n$ letters, where the $i$-th letter specifies what surname the original ancestor $i$ had. Both strings consist only of lowercase English letters, i.e., a, b, ..., z, without any spaces.
The next $q$ lines contain descriptions of subsequent events. The $i$-th description contains two integers $t_i, k_i$ and a lowercase English letter $b_i$ ($1 \le t_i \le 2$, $1 \le k_i \le 2^n$). If $t_i = 1$, the $i$-th event means changing the $k_i$-th letter of Bajtazar's surname to $b_i$. If $t_i = 2$, the $i$-th event means changing the surname of the original ancestor $k_i$ to $b_i$.
Output
Your program should output $q+1$ lines. The first line should contain the answer corresponding to the situation before any events, while the subsequent $q$ lines should contain the answers after the given events, in the same order as they were described in the input.
The answer is the word TAK if Bajtazar's current surname could have been formed from the surnames in the current archival record according to the surname formation rules, or NIE otherwise.
Examples
Input 1
2 4 abcd cadb 1 2 c 2 4 c 1 1 d 1 4 a
Output 1
NIE NIE TAK NIE TAK
Note
Explanation of the example: Here are Bajtazar's records before all events and after subsequent events:
- Bajtazar has the surname abcd, and his grandparents were to have surnames c, a, d, b respectively. Answer NIE.
- Bajtazar has the surname accd, and his grandparents were to have surnames c, a, d, b respectively. Answer NIE.
- Bajtazar has the surname accd, and his grandparents were to have surnames c, a, d, c respectively. Answer TAK. Bajtazar's parents had surnames ac and cd respectively; see the drawing.
- Bajtazar has the surname dccd, and his grandparents were to have surnames c, a, d, c respectively. Answer NIE.
- Bajtazar has the surname dcca, and his grandparents were to have surnames c, a, d, c respectively. Answer TAK. Bajtazar's parents had surnames ca and dc respectively.
