1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
pi operator+(const pi &a, const pi &b){
    return {a.first + b.first,a.second + b.second};
}
vector <pi> dir;
bool ok(const pi &a, int n, int m){
    if(!(a.first < n && a.first >= 0))return 0;
    if(!(a.second < m && a.second >= 0))return 0;
    return 1;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = -1; i <= 1; ++i){
        for(int j = -1; j <= 1; ++j){
            if(i != 0 || j != 0)dir.push_back({i,j});
        }
    }
    map <pi, int> M;
    int n, m, k;
    cin >> n >> m >> k;
    vector <int> bity = {2,4};
    vector <int> kolxmin4(n,1e9),kolxmax2(n,-100),wierymin2(m,1e9), wierymax4(m,-100);
    vector <set <int> > kolx(n), wiery(m);
    function<void(pi, int)> dfs = [&](pi x, int bit){
        if((M[x] & bit) == bit)return;
        M[x] |= bit;
        vector <pi> sa;
        {
            int g1 = x.first;
            int g2 = x.second;
            if(bit & 2){
                kolxmax2[g1] = max(kolxmax2[g1], g2);
                wierymin2[g2] = min(wierymin2[g2], g1);
            }
            if(bit & 4){
                kolxmin4[g1] = min(kolxmin4[g1], g2);
                wierymax4[g2] = max(wierymax4[g2], g1);
            }
        }
        if(bit & 2){
            int g1 = x.first -1;
            int g2 = x.second + 1;
            if(g2 >= 0 && g2 < m){
                auto it = wiery[g2].lower_bound(g1);
                if(it != wiery[g2].end()){
                    sa.push_back({*it,g2});
                }
            }
            if(g1 >= 0 && g1 < n){
                auto it = kolx[g1].lower_bound(g2);
                if(it != kolx[g1].begin() && kolx[g1].size()){
                    --it;
                    sa.push_back({g1,*it});
                }
            }
        }
        if(bit & 4){
            int g1 = x.first + 1;
            int g2 = x.second - 1;
            if(g2 >= 0 && g2 < m){
                auto it = wiery[g2].lower_bound(g1);
                if(wiery[g2].size() && it != wiery[g2].begin()){
                    --it;
                    sa.push_back({*it,g2});
                }
            }
            if(g1 >= 0 && g1 < n){
                auto it = kolx[g1].lower_bound(g2);
                if(it != kolx[g1].end()){
                    sa.push_back({g1,*it});
                }
            }
        }
        for(auto t : sa){
            if(ok(t, n, m)){
                if(M.count(t)){
                    dfs(t, bit);
                }
            }
        }
    };
    vector <int> forbidden_bits = {2|4};
    int x=0;
    for(int i = 0; i < k; ++i){
        int r,c,z;
        cin >> r >> c >> z;
        pi u = {(r^x)%n, (c^x)%m};
        int s = 1;
        if(u.first == 0)s |= 4;
        if(u.first == n-1)s |= 2;
        if(u.second == 0)s |= 2;
        if(u.second == m-1)s |= 4;
        {
            int g1 = u.first -1;
            int g2 = u.second + 1;
            if(g2 >= 0 && g2 < m){
                int h = wierymax4[g2];
                if(h >= g1)s |= 4;
            }
            if(g1 >= 0 && g1 < n){
                int h = kolxmin4[g1];
                if(h <= g2)s |= 4;
            }
        }
        {
            int g1 = u.first + 1;
            int g2 = u.second - 1;
            if(g2 >= 0 && g2 < m){
                int h = wierymin2[g2];
                if(h <= g1)s |= 2;
            }
            if(g1 >= 0 && g1 < n){
                int h = kolxmax2[g1];
                if(h >= g2)s |= 2;
            }

        }
        bool a = 0;
        for(int f : forbidden_bits){
            if((s & f) == f){
                a = 1;
            }
        }
        if(a){
            cout << "TAK\n";
            x ^= z;
        }
        else {
            M[u] = 0;
            wiery[u.second].insert(u.first);
            kolx[u.first].insert(u.second);
            dfs(u,s);
            cout <<"NIE\n";
        }
    } 
    
    //  m|
    //   |-> n
    //    4
    //  4   2
    //    2
}