C. Орак и Game of Life
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти в этой задаче.

Орак любит игры. Недавно он придумал новую игру, «Game of Life».

Вы должны играть в эту игру на черно-белом клетчатом поле из $$$n$$$ строк и $$$m$$$ столбцов. Каждая клетка либо белая, либо черная.

На каждой итерации этой игры (исходная итерация это $$$0$$$) цвет клетки будет изменяться по следующим правилам:

  • Если на текущей итерации нет соседних клеток с таким же цветом, как и эта клетка, ее цвет на следующей итерации останется прежним.
  • Иначе, ее цвет на следующей итерации будет другим.

Две клетки являются соседними, если у них есть общая сторона.

Орак уже выбрал исходное состояние игры, и он хочет знать для клетки $$$(i,j)$$$ (в $$$i$$$-й строке и $$$j$$$-м столбце), чему будет равен ее цвет на итерации $$$p$$$. Он может задавать вам эти вопросы по несколько раз.

Входные данные

В первой строке записано три целых числа $$$n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$$$, описывающие количество строк и столбцов, и количество запросов Орака.

Каждая из следующих $$$n$$$ строк содержит бинарную строку длины $$$m$$$, $$$j$$$-й символ в $$$i$$$-й строке описывает изначальный цвет клетки $$$(i,j)$$$. '0' означает белый, '1' означает черный.

Каждая из следующих $$$t$$$ строк содержит три целых числа $$$i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$$$, описывающие запрос Орака.

Выходные данные

Выведите $$$t$$$ строк, в $$$i$$$-й из которых вы должны вывести ответ на $$$i$$$-й запрос Орака. Если цвет клетки черный, вы должны вывести '1', иначе, вы должны вывести '0'.

Примеры
Входные данные
3 3 3
000
111
000
1 1 1
2 2 2
3 3 3
Выходные данные
1
1
1
Входные данные
5 2 2
01
10
01
10
01
1 1 4
5 1 4
Выходные данные
0
0
Входные данные
5 5 3
01011
10110
01101
11010
10101
1 1 4
1 2 3
5 5 3
Выходные данные
1
0
1
Входные данные
1 1 3
0
1 1 1
1 1 2
1 1 3
Выходные данные
0
0
0
Примечание

В первом примере картинка выше описывает исходну ситуацию и цвета клеток на итерациях $$$1$$$, $$$2$$$, и $$$3$$$. Вы можете увидеть, что цвет клетки $$$(1,1)$$$ на итерации $$$1$$$ черный, цвет клетки $$$(2,2)$$$ после итерации $$$2$$$ черный, и цвет клетки $$$(3,3)$$$ после итерации $$$3$$$ тоже черный.

Во втором примере можно доказать, что клетки никогда не поменяют свой цвет.