Это задача с двойным запуском

На складе фей Найгглато приготовила для Ктолли и Виллема необычную игру.

Их разделили, чтобы они не могли общаться. У них есть только чёрно-белая картинка — которую Найгглато может сдвигать, поворачивать, отражать или даже менять цвета.

Найгглато считала это проверкой способности коммуникации. Ктолли и Виллем, возможно, видели в этой игре лишь цель — как бы ни менялся мир, они всё равно должны найти одно и то же место.

В игру играет два игрока — Ктолли и Виллем. Жюри, в лице Найгглато, сначала общается с Ктолли. После того как Ктолли закончит, жюри общается с Виллемом. Ктолли и Виллем могут заранее договориться о стратегии, которую будут использовать, но они не могут напрямую передавать информацию друг другу.

В каждом наборе входных данных Найгглато готовит чёрно-белую картинку, состоящую из $$$n \times n$$$ ячеек, и выбирает целевую ячейку $$$x$$$. Строки и столбцы пронумерованы от $$$1$$$ до $$$n$$$.

Картинка содержит $$$w$$$ чёрных ячеек. Гарантируется, что $$$\gcd(n,w)=1$$$.

Сначала Найгглато показывает картинку и целевую ячейку $$$x$$$ Ктолли. Ктолли должна выбрать две ячейки и поменять их цвета местами. Эти две ячейки могут совпадать. Если они совпадают или имеют одинаковый цвет, картинка не изменяется. Она не может передать Виллему никакой другой информации.

При замене цветов целевая ячейка не перемещается.

Затем Найгглато незаметно преобразует изображение. Она может выполнить следующие операции любое количество раз (в том числе ноль) в любом порядке:

1. Выбрать два целых числа $$$d_r$$$ и $$$d_c$$$ ($$$0\le d_r,d_c \lt n$$$) и выполняет циклический сдвиг изображения. Каждая ячейка $$$(r,c)$$$ перемещается в точку $$$\left(\left(r-1+d_r\right)\bmod n+1,\left(c-1+d_c\right)\bmod n+1\right)$$$;
2. Повернуть изображение по часовой стрелке на $$$90^\circ$$$. Одно такое вращение перемещает каждую ячейку $$$(r,c)$$$ в точку $$$(c,n+1-r)$$$;
3. Отразить изображение относительно его вертикальной оси. Такое отражение перемещает каждую ячейку $$$(r,c)$$$ в точку $$$(r,n+1-c)$$$;
4. Инвертировать все цвета. При этом каждая чёрная ячейка превращается в белую, а каждая белая — в чёрную.

Целевая ячейка $$$x$$$ подвергается каждому циклическому сдвигу, повороту и отражению точно так же, как и изображение. Инверсия цветов не приводит к её перемещению.

Наконец, Найгглато показывает Виллему только итоговое изображение. Виллем должен определить итоговое положение $$$x$$$.

Ваша программа будет запускаться ровно два раза для каждого теста. При первом запуске она должна действовать как Ктолли. При втором запуске она должна действовать как Виллем. Между двумя запусками не сохраняется никакой информации, за исключением информации, переданной жюри в соответствии с приведёнными выше правилами.

Порядок наборов входных данных может меняться между двумя запусками.

Первый запуск

На первом запуске вы играете за Ктолли.

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

Первая строка содержит строку first, указывающую, что это первый запуск.

После этой строки остальные входные данные имеют следующий формат.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 800$$$) — высоту и ширину картинки.

Каждая из следующих $$$n$$$ строк содержит строку длиной $$$n$$$. Символ $$$\mathtt{\#}$$$ обозначает чёрную ячейку, а символ $$$\mathtt{.}$$$ — белую ячейку.

Следующая строка содержит два целых числа $$$r_x$$$ и $$$c_x$$$ ($$$1 \le r_x,c_x \le n$$$) — номер строки и столбца целевой ячейки $$$x$$$.

Пусть $$$w$$$ — количество чёрных ячеек на картинке. Гарантируется, что $$$\gcd(n,w)=1$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$800^2$$$.

Вывод

Для каждого набора входных данных выведите четыре целых числа $$$r_1$$$, $$$c_1$$$, $$$r_2$$$ и $$$c_2$$$ ($$$1 \le r_1,c_1,r_2,c_2 \le n$$$) — две ячейки, цвета которых Ктолли решает поменять местами. Эти две ячейки могут совпадать.

Второй запуск

На втором запуске вы играете за Виллема.

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

В первой строке содержится строка second, указывающая, что это второй запуск.

После этой строки остальные входные данные имеют следующий формат.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Значение $$$t$$$ такое же, как и в первом запуске, хотя наборы входных данных могут идти в другом порядке.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 800$$$).

Каждая из следующих $$$n$$$ строк содержит строку длиной $$$n$$$, описывающую итоговую картинку после перестановки Ктолли и преобразований Найгглато для соответствующего набора входных данных из первого запуска. Опять же, символ $$$\mathtt{\#}$$$ обозначает чёрную ячейку, а $$$\mathtt{.}$$$ — белую.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$800^2$$$.

Вывод

Для каждого набора входных данных выведите два целых числа $$$r'_x$$$ и $$$c'_x$$$ ($$$1 \le r'_x,c'_x \le n$$$) — строку и столбец целевой ячейки после всех преобразований.

В этой задаче отключены взломы.