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
#include <iostream>
#include <list>
#include <set>
#include <unordered_map>
#include <stack>

struct Point {
    unsigned long long n;
    unsigned long long m;

    bool operator==(const Point &other) const {
        return (n == other.n && m == other.m);
    }
};

int main()
{
    unsigned long long n, m, fortsCount;
    std::cin >> n;
    std::cin >> m;
    std::cin >> fortsCount;
    unsigned long long currXor = 0;
    bool** fortsPlaced = static_cast<bool **>(calloc(n, sizeof(bool *)));
    for (int i = 0; i < n; i++) {
        fortsPlaced[i] = static_cast<bool *>(calloc(m, sizeof(bool)));
    }
    for (unsigned long long f = 0; f < fortsCount; f++) {
        unsigned long long r, c, z;
        std::cin >> r;
        std::cin >> c;
        std::cin >> z;
        unsigned long long currN = (r ^ currXor) % n;
        unsigned long long currM = (c ^ currXor) % m;
        fortsPlaced[currN][currM] = true;

        bool** visited = static_cast<bool **>(calloc(n, sizeof(bool *)));
        for (int i = 0; i < n; i++) {
            visited[i] = static_cast<bool *>(calloc(m, sizeof(bool)));
        }

        std::stack<Point> stack;
        stack.push(Point{0, 0});
        Point p = {INT32_MAX, INT32_MAX};
        while (!stack.empty() && !(p == Point{n-1, m-1})) {
            p = stack.top();
            stack.pop();

            if (p.n < n-1 && !fortsPlaced[p.n+1][p.m]
                && !visited[p.n + 1][p.m]) {
                visited[p.n + 1][p.m] = true;
                stack.push(Point{p.n + 1, p.m});
            }
            if (p.m < m-1 && !fortsPlaced[p.n][p.m + 1]
                && !visited[p.n][p.m + 1]) {
                visited[p.n][p.m + 1] = true;
                stack.push(Point{p.n, p.m + 1});
            }
        }

        if (!visited[n-1][m-1]) {
            currXor ^= z;
            fortsPlaced[currN][currM] = false;
            std::cout << "TAK" << std::endl;
        } else {
            std::cout << "NIE" << std::endl;
        }
        for (int i = 0; i < n; i++) {
            free(visited[i]);
        }
        free(visited);
    }
    for (int i = 0; i < n; i++) {
        free(fortsPlaced[i]);
    }
    free(fortsPlaced);
    return 0;
}