Пинк Флойд устраивают розыгрыш Роджера Уотерса. Они знают, что ему не нравятся стены, он хочет иметь возможность свободно ходить, поэтому они запрещают ему выходить из своей комнаты, которую можно рассматривать как таблицу.

У Роджера Уотерса есть квадратная таблица размером $$$n\times n$$$ и он хочет добраться из левого верхнего угла ($$$1,1$$$) своей таблицы в правый нижний угол ($$$n,n$$$). Уотерс может перемещаться от клетки к любой другой клетке, смежной с ней по стороне, и не может выходить за пределы таблицы. Также за исключением клеток ($$$1,1$$$) и ($$$n,n$$$) в каждой клетке записано значение $$$0$$$ или $$$1$$$.

Перед началом своего обхода он выберет либо $$$0$$$, либо $$$1$$$ и сможет переходить только по клеткам, значения в которых равны выбранной им цифре. Начальная и конечная клетки ($$$1,1$$$) и ($$$n,n$$$)  — исключения из этого правила, он может проходить через них независимо от выбранной цифры. В клетке ($$$1, 1$$$) записана буква 'S', а в клетке ($$$n, n$$$)  — буква 'F'.

Например, в первом примере теста он может перейти от ($$$1,1$$$) к ($$$n,n$$$), используя нули на этом пути: ($$$1, 1$$$), ($$$2, 1$$$), ($$$2, 2$$$), ($$$2, 3$$$), ($$$3, 3$$$), ($$$3, 4$$$), ($$$4, 4$$$)

Остальная часть группы (Пинк Флойд) хочет, чтобы Уотерс не смог совершить свой обход, поэтому пока он не видит, они инвертируют максимум две клетки в таблице (из $$$0$$$ на $$$1$$$ или наоборот). Они боятся, что могут не успеть и просят вашей помощи в выборе клеток. Заметьте, что вы не можете инвертировать клетки $$$(1, 1)$$$ и $$$(n, n)$$$.

Можно показать, что для данных ограничений решение всегда существует.

Также обратите внимание, что Уотерс выберет свою цифру обхода после того, как группа изменит свою таблицу, поэтому он не должен быть в состоянии достичь ($$$n,n$$$) независимо от того, какую цифру он выберет.