**Please notice the unusual memory limit of this problem.**

Orac likes games. Recently he came up with the new game, “Game of Life”.

You should play this game on a black and white grid with $n$ rows and $m$ columns. Each cell is either black or white.

For each iteration of the game (the initial iteration is $0$), the color of each cell will change under the following rules:

- If there are no adjacent cells with the same color as this cell on the current iteration, the color of it on the next iteration will be the same.
- Otherwise, the color of the cell on the next iteration will be different.

Two cells are adjacent if they have a mutual edge.

Now Orac has set an initial situation, and he wants to know for the cell $(i,j)$ (in $i$-th row and $j$-th column), what will be its color at the iteration $p$. He may ask you these questions several times.Input

The first line contains three integers $n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$, representing the number of rows, columns, and the number of Orac queries.

Each of the following $n$ lines contains a binary string of length $m$, the $j$-th character in $i$-th line represents the initial color of cell $(i,j)$. ‘0’ stands for white, ‘1’ stands for black.

Each of the following $t$ lines contains three integers $i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$, representing a query from Orac.Output

Print $t$ lines, in $i$-th line you should print the answer to the $i$-th query by Orac. If the color of this cell is black, you should print ‘1’; otherwise, you should write ‘0’.Examplesinput

3 3 3 000 111 000 1 1 1 2 2 2 3 3 3

output

1 1 1

input

5 2 2 01 10 01 10 01 1 1 4 5 1 4

output

0 0

input

5 5 3 01011 10110 01101 11010 10101 1 1 4 1 2 3 5 5 3

output

1 0 1

input

1 1 3 0 1 1 1 1 1 2 1 1 3

output

0 0 0

Note

For the first example, the picture above shows the initial situation and the color of cells at the iteration $1$, $2$, and $3$. We can see that the color of $(1,1)$ at the iteration $1$ is black, the color of $(2,2)$ at the iteration $2$ is black, and the color of $(3,3)$ at the iteration $3$ is also black.

For the second example, you can prove that the cells will never change their colors.

**Solution:**

#include <bits/stdc++.h> using namespace std; const int di[4] = {-1, 0, 1, 0}; const int dj[4] = {0, -1, 0, 1}; int main() { ios::sync_with_stdio(false); cin.tie(0); int h, w, t; cin >> h >> w >> t; vector<string> s(h); for (int i = 0; i < h; i++) { cin >> s[i]; } vector<vector<int>> when(h, vector<int>(w, -1)); vector<pair<int, int>> que; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { for (int dir = 0; dir < 4; dir++) { int ni = i + di[dir]; int nj = j + dj[dir]; if (ni >= 0 && nj >= 0 && ni < h && nj < w) { if (s[ni][nj] == s[i][j]) { que.emplace_back(i, j); when[i][j] = 0; break; } } } } } for (int b = 0; b < (int) que.size(); b++) { int i = que[b].first; int j = que[b].second; for (int dir = 0; dir < 4; dir++) { int ni = i + di[dir]; int nj = j + dj[dir]; if (ni >= 0 && nj >= 0 && ni < h && nj < w) { if (when[ni][nj] == -1) { que.emplace_back(ni, nj); when[ni][nj] = when[i][j] + 1; } } } } while (t--) { int i, j; long long p; cin >> i >> j >> p; --i; --j; if (when[i][j] == -1 || p < when[i][j] || (p - when[i][j]) % 2 == 0) { cout << s[i][j] << '\n'; } else { cout << (char) (s[i][j] ^ 1) << '\n'; } } return 0; }