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
#include <iostream>
#include <queue>
using namespace std;

bool mapa [10000+5][10000+5];
int odl [10000+5][10000+5];

queue < pair <pair<int, int> , int> > Q;

int options[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k;
    cin>>n>>m>>k;

    int x = 0;
    int r, c, z;
    bool B, ok;
    int top_x, top_y, top_dist, sas_x, sas_y;

    for(int t=1; t<=k; t++)
    {
        cin>>r>>c>>z;
        r = int(r ^ x);
        c = int(c ^ x);
        r%=n;
        c%=m;

        for(int i=0; i<=(n+1); i++)
            for(int j=0; j<=(m+1); j++)
                odl[i][j] = -1;

        r++;
        c++;

        mapa[r][c] = 1;

        while(!Q.empty())
            Q.pop();

        Q.push(make_pair(make_pair(1,1), 0));
        odl[1][1] = 0;

        B = 0;
        ok = 0;

        while(!Q.empty() && !B)
        {
            top_x = Q.front().first.first;
            top_y = Q.front().first.second;
            top_dist = Q.front().second;
            Q.pop();

            for(int i=0; i<4; i++)
            {
                sas_x = top_x+options[i][0];
                sas_y = top_y+options[i][1];

                if(mapa[sas_x][sas_y] == 0)
                    if(odl[sas_x][sas_y] == (-1))
                        if(sas_x>0 && sas_x<=n && sas_y>0 && sas_y<=m)
                        {
                            odl[sas_x][sas_y] = top_dist+1;
                            Q.push(make_pair(make_pair(sas_x,sas_y), top_dist+1));
                            if(sas_x == n && sas_y == m)
                            {
                                B=1;
                                if((top_dist+1) == (n+m-2))
                                    ok=1;
                                else
                                    ok=0;
                            }
                        }
            }
        }

        if(ok)
            cout<<"NIE"<<'\n';

        else
        {
            mapa[r][c] = 0;
            cout<<"TAK"<<'\n';
            x = int(x^z);
        }
    }

    return 0;
}