Обратите внимание на необычное ограничение по памяти в этой задаче.
Орак любит игры. Недавно он придумал новую игру, «Game of Life».
Вы должны играть в эту игру на черно-белом клетчатом поле из \(n\) строк и \(m\) столбцов. Каждая клетка либо белая, либо черная.
На каждой итерации этой игры (исходная итерация это \(0\)) цвет клетки будет изменяться по следующим правилам:
- Если на текущей итерации нет соседних клеток с таким же цветом, как и эта клетка, ее цвет на следующей итерации останется прежним.
- Иначе, ее цвет на следующей итерации будет другим.
Две клетки являются соседними, если у них есть общая сторона.
Орак уже выбрал исходное состояние игры, и он хочет знать для клетки \((i,j)\) (в \(i\)-й строке и \(j\)-м столбце), чему будет равен ее цвет на итерации \(p\). Он может задавать вам эти вопросы по несколько раз.
Выходные данные
Выведите \(t\) строк, в \(i\)-й из которых вы должны вывести ответ на \(i\)-й запрос Орака. Если цвет клетки черный, вы должны вывести '1', иначе, вы должны вывести '0'.
Примечание
В первом примере картинка выше описывает исходну ситуацию и цвета клеток на итерациях \(1\), \(2\), и \(3\). Вы можете увидеть, что цвет клетки \((1,1)\) на итерации \(1\) черный, цвет клетки \((2,2)\) после итерации \(2\) черный, и цвет клетки \((3,3)\) после итерации \(3\) тоже черный.
Во втором примере можно доказать, что клетки никогда не поменяют свой цвет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 3
000
111
000
1 1 1
2 2 2
3 3 3
|
1
1
1
|
|
2
|
5 2 2
01
10
01
10
01
1 1 4
5 1 4
|
0
0
|
|
3
|
5 5 3
01011
10110
01101
11010
10101
1 1 4
1 2 3
5 5 3
|
1
0
1
|
|
4
|
1 1 3
0
1 1 1
1 1 2
1 1 3
|
0
0
0
|