// https://szkopul.edu.pl/problemset/problem/0I18dLrp40xsAiQ-qMLmX-jP/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 2 * (1 << 20) + 3; // 1048576 nodes for n=20

long long d[sizik][2];
std::string s[2];

long long compute_hash(long long a, long long b) {
    if (a < b) swap(a, b);
    return (a * (a + 1LL)) / 2LL + b;
}

void build(int v, int tl, int tr, int tree_num) {
    if (tl == tr) {
        int c = s[tree_num][tl - 1] - 'a' + 1;
        d[v][tree_num] = (c * (c + 1LL)) / 2LL; // b is 0
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm, tree_num);
        build(2 * v + 1, tm + 1, tr, tree_num);
        long long left = d[2 * v][tree_num];
        long long right = d[2 * v + 1][tree_num];
        d[v][tree_num] = compute_hash(left, right);
    }
}

void update(int v, int tl, int tr, int pos, char c_char, int tree_num) {
    if (tl == tr) {
        int c = c_char - 'a' + 1;
        d[v][tree_num] = (c * (c + 1LL)) / 2LL; // b is 0
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2 * v, tl, tm, pos, c_char, tree_num);
        } else {
            update(2 * v + 1, tm + 1, tr, pos, c_char, tree_num);
        }
        long long left = d[2 * v][tree_num];
        long long right = d[2 * v + 1][tree_num];
        d[v][tree_num] = compute_hash(left, right);
    }
}

bool check() {
    return d[1][0] == d[1][1];
}

int zll;

void check_a_print() {
    if (check()) {
        std::cout << "TAK\n";
    } else {
        std::cout << "NIE\n";
    }
}

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::cin >> s[0] >> s[1];

    zll = 1 << n;

    build(1, 1, zll, 0);
    build(1, 1, zll, 1);

    check_a_print();

    for (; q > 0; q--) {
        int t, k;
        char b;
        std::cin >> t >> k >> b;
        t--;

        update(1, 1, zll, k, b, t);

        check_a_print();
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    for (; t > 0; t--) {
        solve();
    }

    return 0;
}