1. const int INF = (1 << 30);

  2. const int NMAX = 1005;

  3. int N, M, T;

  4. char s[NMAX][NMAX];

  5. bool bad[NMAX][NMAX];

  6. bool seen[NMAX][NMAX];

  7. int dist[NMAX][NMAX];

  8. char color[NMAX][NMAX];

  9. int dx[] = {-1, 1, 0, 0};

  10. int dy[] = {0, 0, -1, 1};


  12. bool Inside(int i, int j)

  13. {

  14. return 1 <= i && i <= N && 1 <= j && j <= M;

  15. }


  17. int Fill(int startx, int starty, char val)

  18. {

  19. int cnt = 1;

  20. stack <pii> st;

  21. st.push(mp(startx, starty));

  22. seen[startx][starty] = true;

  23. while (!st.empty())

  24. {

  25. int i = st.top().first;

  26. int j = st.top().second;

  27. st.pop();

  28. for (int k = 0; k < 4; ++k)

  29. {

  30. int x = i + dx[k];

  31. int y = j + dy[k];

  32. if (Inside(x, y) && seen[x][y] == false && s[x][y] == val)

  33. {

  34. st.push(mp(x, y));

  35. seen[x][y] = true;

  36. ++cnt;

  37. }

  38. }

  39. }

  40. return cnt;

  41. }


  43. int main()

  44. {

  45. #ifndef ONLINE_JUDGE

  46. ifstream cin("test.in");

  47. #endif

  48. #ifdef ONLINE_JUDGE

  49. ios_base::sync_with_stdio(false);

  50. cin.tie(nullptr);

  51. #endif

  52. cin >> N >> M >> T;

  53. for (int i = 1; i <= N; ++i)

  54. cin >> (s[i] + 1);

  55. for (int i = 1; i <= N; ++i)

  56. for (int j = 1; j <= M; ++j)

  57. {

  58. if (seen[i][j] == false)

  59. if (Fill(i, j, s[i][j]) == 1)

  60. bad[i][j] = true;

  61. }

  62. queue <pair <pii ,char>> q;

  63. for (int i = 1;i <= N;++i)

  64. for (int j = 1; j <= M; ++j)

  65. {

  66. color[i][j] = s[i][j];

  67. if (bad[i][j])

  68. dist[i][j] = INF;

  69. else

  70. {

  71. dist[i][j] = 0;

  72. q.push(mp(mp(i, j), s[i][j]));

  73. }

  74. }

  75. while (!q.empty())

  76. {

  77. int i = q.front().first.first;

  78. int j = q.front().first.second;

  79. char from = q.front().second;

  80. q.pop();

  81. for (int k = 0; k < 4; ++k)

  82. {

  83. int x = i + dx[k];

  84. int y = j + dy[k];

  85. if (Inside(x, y) && dist[x][y] > dist[i][j] + 1)

  86. {

  87. color[x][y] = from;

  88. dist[x][y] = dist[i][j] + 1;

  89. q.push(mp(mp(x, y), from));

  90. }

  91. }

  92. }

  93. while (T-- > 0)

  94. {

  95. long long i, j, p;

  96. cin >> i >> j >> p;

  97. if (dist[i][j] == INF || p <= dist[i][j])

  98. cout << (s[i][j] - '0') << "\n";

  99. else

  100. {

  101. p -= dist[i][j];

  102. if (p % 2)

  103. cout << ('1' - s[i][j]) << "\n";

  104. else

  105. cout << (s[i][j] - '0') << "\n";

  106. }

  107. }

  108. #ifndef ONLINE_JUDGE

  109. cout << "\n\n\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

  110. cin.close();

  111. #endif

  112. return 0;

  113. }