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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double ld;
const LL p = 1000000007;
const char Port = 1;
const char Pogorzelisko = 2;
const char Warownia = 3;
const int N = 100001;

bool findAnyBestPath(vector<char>& mapa, int n, int m) {
    std::queue<pair<int, int>> paths;
    paths.push(make_pair(0, 1));
    while(!paths.empty()) {
        auto el = paths.front();
        auto p = el.first;
        int len = el.second;
        int x = p / m;
        int y = p % m;
        paths.pop();

        if (len == n+m-1 && x == n-1 && y == m-1) {
            return true;
        }
        if (x+1 < n && mapa[p + m] != Warownia) {
            paths.push(make_pair(p + m, len+1));
        }
        if (y+1 < m && mapa[p + 1] != Warownia) {
            paths.push(make_pair(p + 1, len+1));
        }
    }
    return false;
} 

int main() {
    std::ios::sync_with_stdio(false);
    int n, m, k, r, c, z;
    int x = 0;
    cin >> n >> m >> k;
        vector<char> mapa;
        mapa.resize(n*m);
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                mapa[i*m + j] = 0;      
            }
        }
        mapa[0] = Port;
        mapa[n*m - 1] = Port;

        for(int i=0; i<k; i++) {
            cin >> r >> c >> z;
            int ri = (r ^ x) % n;
            int ci = (c ^ x) % m;
            mapa[ri*m + ci] = Warownia;
            if (findAnyBestPath(mapa, n, m)) {
                cout << "NIE" << endl;
            } else {
                cout << "TAK" << endl;
                mapa[ri*m + ci] = Pogorzelisko;
                x = x ^ z;
            }
        }
    
    return 0;
}