Кубик Рубика
Сашко, освоивший сборку кубика Рубика и стремящийся к новым достижениям, придумал свою собственную головоломку. Однако пока он не знает, как её решить. Вот что он рассказывает о своей головоломке.
Квадратная таблица размером 2n на 2n заполнена натуральными числами, не превышающими 100. За один шаг можно зеркально отразить («перевернуть») любой ряд или столбец таблицы. Ниже приведены примеры выполнения такой операции: слева показано начальное состояние таблицы, а справа — три примера таблиц после выполнения одного из возможных ходов. Выделен ряд или столбец, который был зеркально отражён.
Необходимо определить, можно ли с помощью таких операций получить таблицу, в которой в каждом из четырёх угловых квадратов размером n на n будут записаны одинаковые числа. Числа в разных угловых квадратах могут отличаться. Если это возможно, нужно указать последовательность операций, приводящих к желаемому результату. Например, такую таблицу:
можно преобразовать в нужный вид за 4 шага (выделены ряды и столбцы, над которыми была выполнена операция на предыдущем шаге):
Определите, возможно ли преобразовать таблицу с данным начальным заполнением в нужный вид. Если это возможно, укажите последовательность ходов, после которых таблица приобретает нужный вид.
Входные данные
В первой строке входного файла указано число t — количество тестов, данные к которым приведены в файле. Далее следуют t одинаковых по формату блоков, описывающих тесты. Пустых строк между блоками нет.
В первой строке каждого блока указано натуральное число n.
В следующих 2n строках блока содержится по 2n натуральных чисел, задающих начальное заполнение таблицы. При этом 1 ≤ t ≤ 10, 1 ≤ n ≤ 100, а каждое из чисел в ячейках таблицы — натуральное и не превышает 100.
Выходные данные
Выходной файл должен состоять из t одинаковых по формату блоков, соответствующих t тестам, приведённым во входном файле. Порядок блоков должен быть сохранён: первый блок выходного файла должен соответствовать первому блоку входного, второй блок — второму, и так далее. Пустых строк между блоками не должно быть.
В первой строке каждого блока нужно указать число k — количество операций, после которых таблица приобретёт нужный вид.
В следующих k строках блока нужно описать соответствующие операции в порядке выполнения следующим образом: указать номер ряда или столбца, над которым была выполнена операция. Нумерация начинается с единицы, столбцы считаются слева направо, а ряды — сверху вниз. Если зеркально отражается ряд, перед его номером ставится знак "+" (без кавычек), если столбец — знак "–".
Если начальное расположение чисел в ячейках таблицы не позволяет привести её к нужному виду, единственная строка блока должна содержать число "–1".