← 返回题目列表

Codeforces · 1349/C

C. Orac 和生命游戏

中文机器翻译题面 查看原题

请注意此问题的异常内存限制。

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$$$的颜色也是黑色。

对于第二个示例,您可以证明单元格永远不会改变其颜色。