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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

long n, m, k;
long r, c, z;
long x;

typedef pair<int, int> Pair;
typedef pair<double, pair<int, int>> pPair; 

struct cell {
    int parent_i, parent_j; 
    double f, g, h;
    bool blocked;
}; 

vector<pair<int, int>> path;
cell** grid;
set<Pair> closedList;
set<pPair> openList;

double calculateHValue(int row, int col, Pair dest) {
    return sqrt((row-dest.first)*(row-dest.first) + (col-dest.second)*(col-dest.second)); 
} 

void tracePath(Pair dest) {
  //  printf("trace path\n");
    int row = dest.first; 
    int col = dest.second; 
  
    while (!(grid[row][col].parent_i == row 
             && grid[row][col].parent_j == col )) 
    { 
        path[row+col] = make_pair (row, col); 
        int temp_row = grid[row][col].parent_i; 
        int temp_col = grid[row][col].parent_j; 
        row = temp_row; 
        col = temp_col; 
    }
    // for (int i=0; i<path.size(); i++) {
    //   printf("%ld %ld\n", path[i].first, path[i].second);
    // }
}

bool aStarSearch(Pair src, Pair dest) {
    closedList.clear();
    openList.clear();

    int i = src.first;
    int j = src.second; 
    grid[i][j].f = 0.0;
    grid[i][j].g = 0.0;
    grid[i][j].h = 0.0;
    grid[i][j].parent_i = i; 
    grid[i][j].parent_j = j; 
  
    openList.insert(make_pair (0, make_pair (i, j))); 

    while (!openList.empty()) {
        pPair p = *openList.begin(); 
        openList.erase(openList.begin()); 
  
        // Add this vertex to the closed list 
        Pair current = p.second;
        i = current.first; 
        j = current.second;
        closedList.insert(current);
        vector<Pair> nextFields {make_pair(i+1, j), make_pair(i, j+1)};

        for (int u=0; u<nextFields.size(); u++) {
          Pair next = nextFields[u];
          if (next.first< n && next.second < m) {
              if (next.first == n-1 && next.second == m-1) {
                  grid[next.first][next.second].parent_i = i; 
                  grid[next.first][next.second].parent_j = j; 
                  tracePath(dest);
                  return true; 
              }
              else {
                bool isInClosedList = closedList.find(next) != closedList.end();
                if (!isInClosedList && grid[next.first][next.second].blocked == false) { 
                    double gNew = grid[i][j].g + 1.0; 
                    double hNew = calculateHValue(next.first, next.second, dest); 
                    double fNew = gNew + hNew; 
      
                    if (!isInClosedList || grid[i+1][j].f > fNew) { 
                        openList.insert( make_pair (fNew, next)); 
                        grid[next.first][next.second].f = fNew; 
                        grid[next.first][next.second].g = gNew; 
                        grid[next.first][next.second].h = hNew; 
                        grid[next.first][next.second].parent_i = i; 
                        grid[next.first][next.second].parent_j = j; 
                    } 
                }
             }
          } 
        }
    }
    return false; 
}

bool solve() {
  Pair src = make_pair(0, 0);
  Pair dest = make_pair(n-1, m-1);
  long _x = (r ^ x) % n;
  long _y = (c ^ x) % m;
  grid[_x][_y].blocked = true;
  if (path[_x+_y].first == _x && path[_x+_y].second == _y) {
    bool newPathFound = aStarSearch(src, dest);
    if (newPathFound) {
      return false;
    } else {
      grid[_x][_y].blocked = false;
      x = x ^ z;
      return true;
    }
  } else {
    return false;
  }
}

void init() {
  scanf("%ld %ld %ld\n", &n, &m, &k);
  grid = new cell*[n];
  for (int i=0; i<n; i++) {
    grid[i] = new cell[m];
    for (int j=0; j<m; j++) {
      grid[i][j].blocked = false;
    }
  }
  for (int i=0; i<n; i++) {
    path.push_back(make_pair(i, 0));
  }
  for(int j=1; j<m; j++) {
    path.push_back(make_pair(n-1, j));
  }
}

int main() {
  init();
  for (int i=0; i<k; i++) {
    //printf("%ld\n", i);
    scanf("%ld %ld %ld\n", &r, &c, &z);
    bool result = solve();
    if (result) {
      printf("TAK\n");
    } else {
      printf("NIE\n");
    }
  }
  return 0;
}