CF1349C.Orac and Game of Life

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.

请注意本题不同寻常的内存限制。

Orac 喜欢游戏。最近他设计了一个新游戏，名为“生命游戏”。

你需要在一个 $n$ 行 $m$ 列的黑白网格上进行此游戏。每个格子非黑即白。

在游戏的每一轮迭代中（初始状态为第 $0$ 轮），每个格子的颜色将根据以下规则发生变化：

• 若当前轮次中，该格子没有与之颜色相同的相邻格子，则它在下一轮的颜色保持不变；
• 否则，它在下一轮的颜色将发生翻转（黑变白，白变黑）。

两个格子相邻当且仅当它们有一条公共边。

现在 Orac 已设定一个初始局面，并希望知道：对于格子 $(i,j)$（即第 $i$ 行、第 $j$ 列），它在第 $p$ 轮迭代时的颜色是什么？他可能会多次向你提出此类询问。

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.

第一行包含三个整数 $n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$，分别表示行数、列数以及 Orac 的查询次数。

接下来的 $n$ 行中，每行包含一个长度为 $m$ 的二进制字符串；其中第 $i$ 行的第 $j$ 个字符表示单元格 $(i,j)$ 的初始颜色。'0' 表示白色，'1' 表示黑色。

接下来的 $t$ 行中，每行包含三个整数 $i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$，表示一次来自 Orac 的查询。

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'.

输出 $t$ 行，第 $i$ 行应输出 Orac 的第 $i$ 个查询的答案。如果该格子的颜色为黑色，则输出 1；否则输出 0。

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.

对于第一个样例，上图展示了初始状态以及第 $1$、$2$ 和 $3$ 次迭代时各格子的颜色。我们可以看到：在第 $1$ 次迭代时，格子 $(1,1)$ 的颜色为黑色；在第 $2$ 次迭代时，格子 $(2,2)$ 的颜色为黑色；在第 $3$ 次迭代时，格子 $(3,3)$ 的颜色也为黑色。

对于第二个样例，你可以证明：所有格子的颜色将永远不会发生变化。