E. Плегма
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это задача с двойным запуском (задача на коммуникацию).

Есть два игрока: Игрок A и Игрок B. Жюри сначала взаимодействует с игроком A. После завершения взаимодействия с игроком A, жюри взаимодействует с игроком B. Обратите внимание, что игрок A и игрок B не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию или получать информацию от жюри, но они могут согласовать стратегию, которую будут использовать для общения.

У жюри есть двумерная бинарная сетка $$$G$$$, которая состоит из $$$n$$$ строк и $$$n$$$ столбцов (каждая ячейка этой сетки имеет значение $$$0$$$ или $$$1$$$). Строка $$$1$$$ — это самая верхняя строка, а столбец $$$1$$$ — это самый левый столбец. Связность этой сетки имеет значение $$$1$$$, если существует путь, идущий влево, вправо, вверх или вниз, проходящий только через ячейки со значением $$$1$$$, соединяющий каждую пару ячеек $$$(i_1,j_1)$$$ и $$$(i_2,j_2)$$$, таких что $$$G_{i_1,j_1}=G_{i_2,j_2}=1$$$. Обратите внимание, что движение по диагонали не допускается. Гарантируется, что в этой сетке существует хотя бы одна ячейка со значением $$$1$$$.

Сначала жюри взаимодействует с игроком A. Жюри даст игроку A сетку $$$G$$$. После осмотра сетки игрок A должен определить два целых числа $$$r$$$ и $$$c$$$ и отправить их жюри. В начале взаимодействия игрока B игрок B получит значения всех ячеек в $$$r$$$-й строке и всех ячеек в $$$c$$$-м столбце от жюри. Обратите внимание, что игроку B не предоставляются значения $$$r$$$ и $$$c$$$.

Игрок A хочет убедиться, что игрок B сможет определить связность $$$G$$$. Ваша задача — действовать как оба игрока и найти стратегию, чтобы игрок B смог правильно определить связность. Обратите внимание, что коммуникатор этой задачи не адаптивен — то есть сетка, предоставленная вам в первом запуске, будет такой же, как сетка, использованная для оценки связности.

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

Ваш код будет выполнен ровно два раза для каждого набора входных данных. В первом запуске вы будете Игроком A, а во втором — Игроком B.

Входные данные первого запуска

Первая строка входных данных содержит строку first. Это нужно для того, чтобы ваша программа распознала, что это её первый запуск, и она должна действовать как Игрок A.

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$C$$$ ($$$2 \leq n \leq 1000, 0 \leq C \leq 1$$$) – размер сетки и связность соответственно.

Следующие $$$n$$$ строк содержат информацию о сетке. $$$i$$$-я из этих строк содержит бинарную строку $$$G_i$$$ длиной $$$n$$$, обозначающую $$$i$$$-ю строку сетки.

Гарантируется, что:

  • Сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^6$$$
  • Значение $$$C$$$ соответствует информации в сетке — то есть, если $$$C=1$$$, то сетка имеет связность $$$1$$$, а если $$$C=0$$$, то сетка имеет связность $$$0$$$.
  • В каждой сетке есть хотя бы одна ячейка со значением $$$1$$$.

Входные данные второго запуска

Первая строка входных данных содержит строку second. Это нужно для того, чтобы ваша программа распознала, что это её второй запуск, и она должна действовать как Игрок B.

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

Первая строка каждого набора входных данных содержит ровно одно целое число $$$n$$$ — размер сетки, заданной в $$$i$$$-м наборе входных данных входных данных первого запуска.

Вторая строка каждого набора входных данных содержит бинарную строку $$$G_{r, 1}G_{r, 2}\ldots G_{r, n}$$$ — содержимое в строке $$$r$$$ сетки. Обратите внимание, что целое число $$$r$$$ отправляется игроком A жюри в конце их взаимодействия в $$$i$$$-м наборе входных данных.

Третья строка каждого набора входных данных содержит бинарную строку $$$G_{1, c}G_{2, c}\ldots G_{n, c}$$$ — содержимое в столбце $$$c$$$ сетки. Обратите внимание, что целое число $$$c$$$ отправляется игроком A жюри в конце их взаимодействия в $$$i$$$-м наборе входных данных.

Взломы

Чтобы совершить взлом, используйте следующий формат:

Первая строка должна содержать одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество сеток. Затем следует $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных должна содержать одно целое число $$$n$$$ $$$(2 \le n \le 1000)$$$ — размер сетки, которую выберет жюри.

Каждая из следующих $$$n$$$ строк должна содержать бинарную строку длины $$$n$$$. $$$i$$$-я из этих строк должна содержать $$$G_{i, 1}G_{i, 2}\ldots G_{i, n}$$$ — $$$i$$$-ю строку сетки, которую выберет жюри.

В каждой сетке должна существовать хотя бы одна ячейка со значением $$$1$$$, и сумма $$$n^2$$$ по всем наборам входных данных не должна превосходить $$$2\cdot 10^6$$$.

Обратите внимание, что связность каждой сетки определяется жюри, и вам не нужно выводить её для взлома.

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

В первом запуске для каждого набора входных данных выведите два целых числа $$$r$$$ и $$$c$$$ ($$$1 \leq r,c \leq n$$$). Это обозначает, что вы хотите, чтобы второй запуск получил $$$r$$$-ю строку и $$$c$$$-й столбец сетки.

Во втором запуске для каждого набора входных данных выведите целое число $$$C$$$ ($$$0 \leq C \leq 1$$$) – связность сетки.

Примеры
Входные данные
first
2
2 1
11
10
2 0
10
01
Выходные данные
2 2
2 1
Входные данные
second
2
2
10
10
2
01
10
Выходные данные
1
0
Примечание

В первом примере входных данных первая сетка следующая:

11
10

В первом запуске мы знаем, что $$$n = 2$$$. После осмотра примера мы можем определить, что связность равна $$$1$$$.

Для целей этого примера предположим, что Игрок A и Игрок B согласовали какую-то стратегию, согласно которой, если связность равна $$$1$$$, то игрок A должен отправить строку и столбец, которые оба заканчиваются на $$$0$$$. В этом случае строка $$$2$$$ и столбец $$$2$$$ удовлетворяют этой стратегии. Обратите внимание, что это пример стратегии для демонстрации, и использование этой стратегии не сработает для всех случаев.

Затем взгляните на второй запуск. Теперь мы Игрок B. Мы получаем, что $$$n = 2$$$ и что выбранная строка имеет значения $$$r = [1, 0]$$$ и выбранный столбец имеет значения $$$c = [1, 0]$$$. Поскольку последнее число в обоих массивах равно $$$0$$$, игрок B использует согласованную стратегию, чтобы определить, что связность равна $$$1$$$.