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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define ld long double
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>

using namespace std;

struct field {
    bool on_path = false;
    bool split = false;
    int war = -1;
    pi last_split = make_pair(-1, -1);
    int mint = -1;
};

struct event {
    int r, c, z;
    bool a = false;
};

vector<event> E;

vector<vector<field> > V;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;

    V.resize(n);
    E.resize(k);
    for (int i = 0; i < n; i++) {
        V[i].resize(m);
    }
    int X = 0, x, y;
    V[0][0].mint = 0;
    for (int i = 0; i < k; i++) {
        cin >> E[i].r >> E[i].c >> E[i].z;
        if (E[i].r % n == 0 && E[i].c % m == 0)
            continue;
        if (E[i].r % n == n - 1 && E[i].c % m == m - 1)
            continue;

        V[E[i].r % n][E[i].c % m].mint = i + 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j >= 1)
                V[i][j].mint = max(V[i][j - 1].mint, V[i][j].mint);
            if (i >= 1)
                V[i][j].mint = max(V[i - 1][j].mint, V[i][j].mint);
        }
    }
    int dx = 0;
    int dy = 0;
    while ((dx == 0 && dy == 0) || V[dx][dy].mint == V[0][0].mint) {
        if (dx < n - 1 && dy < m - 1) {
            if (V[dx][dy + 1].mint > V[dx + 1][dy].mint) {
                dy++;
            } else {
                dx++;
            }
        } else {
            if (dx < n - 1)
                dx++;
            else
                dy++;
        }
    }

    int first_d = V[dx][dy].mint;
    V[dx][dy].mint = V[0][0].mint;
    V[0][0].last_split = make_pair(0, 0);
    V[0][0].on_path = true;
    V[0][0].split = true;
    V[dx][dy].on_path = true;

    for (int i = 0; i <= dx; i++) {
        for (int j = 0; j <= dy; j++) {
            if (V[i][j].mint != V[0][0].mint)
                continue;

            if (j + 1 < m && i + 1 < n && V[i][j + 1].mint == V[0][0].mint && V[i + 1][j].mint == V[0][0].mint) {
                V[i][j].split = true;
                V[i][j + 1].last_split = V[i + 1][j].last_split = make_pair(i, j);
                V[i][j + 1].on_path = V[i + 1][j].on_path = true;
            } else {
                if (j + 1 < m && V[i][j + 1].mint == V[0][0].mint) {
                    if (V[i][j + 1].last_split.fi == -1)
                        V[i][j + 1].last_split = V[i][j].last_split;
                    V[i][j + 1].on_path = true;
                }
                if (i + 1 < n && V[i + 1][j].mint == V[0][0].mint) {
                    if (V[i + 1][j].last_split.fi == -1)
                        V[i + 1][j].last_split = V[i][j].last_split;
                    V[i + 1][j].on_path = true;
                }
            }
        }
    }
    V[dx][dy].mint = first_d;
    //cout << "first: " << dx << " " << dy << " on " << first_d << endl;

    for (int i = dx; i < n; i++) {
        for (int j = dy; j < m; j++) {
            if (V[i][j].mint < first_d)
                continue;

            if (j + 1 < m && i + 1 < n && V[i][j + 1].mint >= first_d && V[i + 1][j].mint >= first_d) {
                V[i][j].split = true;
                V[i][j + 1].last_split = V[i + 1][j].last_split = make_pair(i, j);
                V[i][j + 1].on_path = V[i + 1][j].on_path = true;
            } else {
                if (j + 1 < m && V[i][j + 1].mint >= first_d) {
                    if (V[i][j + 1].last_split.fi == -1)
                        V[i][j + 1].last_split = V[i][j].last_split;
                    V[i][j + 1].on_path = true;
                }
                if (i + 1 < n && V[i + 1][j].mint >= first_d) {
                    if (V[i + 1][j].last_split.fi == -1)
                        V[i + 1][j].last_split = V[i][j].last_split;
                    V[i + 1][j].on_path = true;
                }
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++)
    //         cout << V[i][j].on_path << " ";
    //     cout << endl;
    // }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++)
    //         cout << "(" << V[i][j].last_split.fi << ", " << V[i][j].last_split.se << ") ";
    //     cout << endl;
    // }

    for (int q = first_d - 1; q < k; q++) {
        x = (E[q].r ^ X) % n;
        y = (E[q].c ^ X) % m;
        // cout << "Hit " << q + 1 << " on " << x << " " << y << endl;
        if (V[x][y].on_path) {
            if (V[x][y].last_split == V[n - 1][m - 1].last_split || V[x][y].last_split == V[0][0].last_split) {
                E[q].a = true;
                X = X ^ E[q].z;
                // cout << "hit!" << endl;
            } else {
                if (V[x][y].split) {
                    V[x][y].on_path = false;
                    V[x][y].last_split = make_pair(-1, -1);
                    pi split = make_pair(x, y);
                    if (x < n - 1) {
                        dx = x + 1;
                        dy = y;
                        while ((dx != n - 1 || dy != m - 1) && V[dx][dy].last_split == split) {
                            V[dx][dy].on_path = false;
                            V[dx][dy].last_split = make_pair(-1, -1);
							if (dy > 1 && V[dx][dy - 1].on_path) {
                                    V[dx][dy].last_split = V[dx][dy - 1].last_split;
									V[dx][dy].on_path = V[dx][dy - 1].on_path;
								}
							if (dx > 1 && V[dx - 1][dy].on_path) {
                                    V[dx][dy].last_split = V[dx - 1][dy].last_split;
									V[dx][dy].on_path = V[dx - 1][dy].on_path;
								}

                            if (dx < n - 1 && V[dx + 1][dy].last_split == split) {
                                dx++;
                            } else if (dy < m - 1 && V[dx][dy + 1].last_split == split) {
                                dy++;
                            }
                        }
                    }
					if (y < m - 1) {
                        dx = x;
                        dy = y + 1;
                        while ((dx != n - 1 || dy != m - 1) && V[dx][dy].last_split == split) {
                            V[dx][dy].on_path = false;
							V[dx][dy].last_split = make_pair(-1, -1);
							if (dy > 1 && V[dx][dy - 1].on_path) {
                                    V[dx][dy].last_split = V[dx][dy - 1].last_split;
									V[dx][dy].on_path = V[dx][dy - 1].on_path;
								}
							if (dx > 1 && V[dx - 1][dy].on_path) {
                                    V[dx][dy].last_split = V[dx - 1][dy].last_split;
									V[dx][dy].on_path = V[dx - 1][dy].on_path;
								}
                            if (dx < n - 1 && V[dx + 1][dy].last_split == split) {
                                dx++;
                            } else if (dy < m - 1 && V[dx][dy + 1].last_split == split) {
                                dy++;
                            }
                        }
                    }
					if(V[n-1][m-1].last_split == split) {
						// cout<<"MLEM"<<endl;
						if(n-2 >= 0 && V[n-2][m-1].last_split != split)
							V[n-1][m-1].last_split = V[n-2][m-1].last_split;
						if(m-2 >= 0 && V[n-1][m-2].last_split != split)
							V[n-1][m-1].last_split = V[n-1][m-2].last_split;
					}
                } else {
					int minus = 1;
					if(y > 1 && V[x][y-minus].on_path && (x >= n-1 || V[x+1][y-minus].on_path))
						minus++;
					for(int qq=minus; qq>=1; qq--) {
						dx = x;
						dy = y - qq;
						// if(V[dx][dy].on_path == false)
						// 	break;
						pi split = V[dx][dy].last_split;
						while ((dx != split.fi || dy != split.se) && V[dx][dy].last_split == split) {
							if(!V[dx][dy].on_path)
								break;
							V[dx][dy].on_path = false;
							if (dx > 1 && V[dx - 1][dy].last_split == split) {
								dx--;
							} else if (dy > 1 && V[dx][dy - 1].last_split == split) {
								dy--;
							}
						}
					}
					// cout<<"M "<<minus<<endl;
                    dx = x;
                    dy = y;
                    pi split = V[dx][dy].last_split;
                    while ((dx != split.fi || dy != split.se) && V[dx][dy].last_split == split) {
						if(!V[dx][dy].on_path)
								break;
                        V[dx][dy].on_path = false;
                        if (dx > 1 && V[dx - 1][dy].last_split == split) {
                            dx--;
                        } else if (dy > 1 && V[dx][dy - 1].last_split == split) {
                            dy--;
                        }
                    }
                    dx = x;
                    dy = y;
                    while ((dx != n - 1 || dy != m - 1) && V[dx][dy].last_split == split) {
						if(!V[dx][dy].on_path)
								break;
                        V[dx][dy].on_path = false;
                        if (dx < n - 1 && V[dx + 1][dy].last_split == split) {
                            if (dy > 1)
                                V[dx][dy].last_split = V[dx][dy - 1].last_split;
                            dx++;

                        } else if (dy < m - 1 && V[dx][dy + 1].last_split == split) {
                            if (dx > 1)
                                V[dx][dy].last_split = V[dx - 1][dy].last_split;
                            dy++;
                        }
                    }
                    V[dx][dy].on_path = true;
                }
            }
        }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < m; j++)
        //         cout << V[i][j].on_path << " ";
        //     cout << endl;
        // }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < m; j++)
        //         cout << "(" << V[i][j].last_split.fi << ", " << V[i][j].last_split.se << ") ";
        //     cout << endl;
        // }
    }
	for(auto e : E) {
		if(e.a)
			cout<<"TAK"<<endl;
		else
			cout<<"NIE"<<endl;
	}

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++)
    //         cout << V[i][j].mint << " ";
    //     cout << endl;
    // }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++)
    //         cout << V[i][j].on_path << " ";
    //     cout << endl;
    // }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++)
    //         cout << "("<<V[i][j].last_split.fi<<", "<<V[i][j].last_split.se<<") ";
    //     cout << endl;
    // }

    return 0;
}