2146. Игра с монетками

Аня и Бетти играют в следующую игру с монетками. Исходно они выкладывают `m\ times\ n` монеток на столе в виде прямоугольной сетки размером `m\ times\ n`, некоторые монеты оказываются вверх орлом, некоторые – вверх решкой. Будем индексировать монеты сетки парами чисел `(x,\ y)`, где `1\ ≤\ x\ ≤\ m` и `1\ ≤\ y\ ≤\ n`. После этого игроки совершают ходы по очереди, Аня ходит первой.

Ход игрока состоит в следующем: игрок выбирает монету, которая лежит вверх решкой, и переворачивает ее. Пусть была перевернута монета в позиции `(i,\ j)` (`1\ ≤\ i\ ≤\ m`, `1\ ≤\ j\ ≤\ n`). После этого игрок выбирает также числа `i_1` и `j_1`, для которых выполнены неравенства `0\ ≤\ i_1\ <\ i`, `0\ ≤\ j_1\ <\ j` и переворачивает монеты в позициях `(i_1,\ j)`, `(i,\ j_1)` и `(i_1,\ j_1)` (если какие-либо из этих монет отсутствуют, поскольку одна из координат равна нулю, то эти позиции игнорируются).

Игрок, который не может сделать ход, поскольку все монеты лежат вверх орлом, проигрывает.

По заданному исходному расположению монет выясните, кто выиграет при оптимальной игре обоих игроков, и если это Аня, то какой первый ход она должна сделать.

Первая строка входного файла содержит `m` и `n` (`1\ ≤\ m,\ n\ ≤\ 50`). Следующие `m` строк содержат по `n` символов, `j`-й из них в `i`-й строке равен 1, если монета в позиции `(i,\ j)` лежит решкой вверх и 0, если она лежит орлом вверх.

Первая строка выходного файла должна содержать имя победителя игры (Ann или Betty). Если побеждает Аня, то на второй строке выведите `i` и `j`, а на третьей строке `i_1` и `j_1`. Эти числа должны описывать первый ход, который должна сделать Аня, чтобы выиграть. Если возможных выигрышных ходов несколько, выведите любой.

3 3
000
000
001

Ann
3 3
0 0

2 2
11
01

Betty