请注意此问题的异常内存限制。
Orac喜欢游戏。最近他想出了新游戏“生命游戏”。
您应该在具有 $$$n$$$ 行和 $$$m$$$ 列的黑白网格上玩此游戏。每个单元格要么是黑色的,要么是白色的。
对于游戏的每次迭代(初始迭代为 $$$0$$$),每个单元格的颜色将根据以下规则发生变化:
- 如果当前迭代中没有与该单元格颜色相同的相邻单元格,则下一次迭代时该单元格的颜色将相同。
- 否则,下一次迭代的单元格颜色将会不同。
如果两个单元具有共同的边缘,则它们是相邻的。
现在Orac已经设置了一个初始情况,他想知道单元格$$$(i,j)$$$(在$$$i$$$第行和$$$j$$$第列),在迭代$$$p$$$时它的颜色是什么。他可能会多次问你这些问题。
输入
第一行包含三个整数$$$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 的查询。
输出
打印$$$t$$$行,在第$$$i$$$行中,您应该打印Orac第$$$i$$$第$$$i$$$查询的答案。如果该单元格的颜色为黑色,则应打印“1”;否则,您应该写“0”。
示例
输入 #1
3 3 3 000 111 000 1 1 1 2 2 2 3 3 3
输出 #1
1 1 1
输入 #2
5 2 2 01 10 01 10 01 1 1 4 5 1 4
输出 #2
0 0
输入 #3
5 5 3 01011 10110 01101 11010 10101 1 1 4 1 2 3 5 5 3
输出 #3
1 0 1
输入#4
1 1 3 0 1 1 1 1 1 2 1 1 3
输出#4
0 0 0
注意
对于第一个示例,上图显示了迭代 $$$1$$$、$$$2$$$ 和 $$$3$$$ 时单元格的初始情况和颜色。我们可以看到,$$$(1,1)$$$在迭代$$$1$$$时的颜色是黑色,$$$(2,2)$$$在迭代$$$2$$$的颜色是黑色,$$$(3,3)$$$在迭代$$$3$$$的颜色也是黑色。
对于第二个示例,您可以证明单元格永远不会改变其颜色。