Кубик Рубіка#7128

Кубик Рубіка

1 секунда

32 мегабайти

Складна

Сашко, опанувавши складання кубика Рубіка та прагнучи нових звершень, вигадав власну головоломку. Проте він поки не знає, як її розв'язати. Ось як Сашко описує свою головоломку.

Перед вами квадратна таблиця з $2 n$ клітинками у кожному рядку і $2 n$ клітинками у кожному стовпчику. Кожна клітинка заповнена натуральним числом, що не перевищує $100$ . За один крок дозволено дзеркально відобразити ("перевернути") будь-який рядок або стовпець таблиці. Нижче подано кілька прикладів такої операції: ліворуч подано початковий стан таблиці, а праворуч три приклади таблиці після одного можливого кроку. Виділено рядок або стовпець, який було дзеркально відображено.

Потрібно з'ясувати, чи можна за допомогою таких операцій перетворити таблицю так, щоб у кожному з чотирьох кутових квадратів розміром $n \times n$ n \times n були однакові числа. Числа в різних кутових квадратах можуть різнитися. Якщо це можливо, слід вказати послідовність кроків до бажаного результату. Наприклад, таку таблицю:

можна перетворити до потрібної форми за $4$ кроки (виділено рядки і стовпці, над якими здійснено операцію):

З'ясуйте, чи можливо перетворити таблицю з поданим початковим заповненням на потрібний вигляд. Якщо це можливо, наведіть відповідну послідовність кроків, після яких таблиця набуде потрібної форми.

Вхідні дані

У першому рядку вхідного файлу зазначено число $t$ — кількість тестів. Далі розташовано $t$ однакових за форматом блоків, що описують тести. Порожніх рядків між блоками немає.

У першому рядку кожного блоку зазначено натуральне число $n$ .

У наступних $2 n$ рядках блоку вказано по $2 n$ натуральних чисел, що задають початкове заповнення таблиці. $1 \leq t \leq 10$ 1 \leq t \leq 10, $1 \leq n \leq 100$ 1 \leq n \leq 100, кожне з чисел у клітинках таблиці — натуральне та не перевищує $100$ .

Вихідні дані

Вихідний файл має складатися з $t$ однакових за форматом блоків, що відповідають $t$ тестам із вхідного файлу. Порядок блоків має бути збережено: перший блок вихідного файлу має відповідати першому у вхідному, другий — другому і т.д. Порожніх рядків між блоками не повинно бути.

У першому рядку кожного блоку вкажіть число $k$ — кількість кроків, після яких таблиця набуде потрібного вигляду.

У наступних $k$ рядках блоку опишіть відповідні кроки у порядку виконання. Для кожної операції потрібно вказати номер рядка або стовпця, над яким було виконано дію. Нумерація починається з одиниці, стовпці нумеруються зліва направо, рядки — згори вниз. Якщо відображається рядок, перед його номером ставиться знак "+" (без лапок), якщо стовпець — знак "–".

Якщо початкове розташування чисел у клітинках не дозволяє привести таблицю до потрібного вигляду, єдиний рядок блоку має містити число "–1".

Приклади

Приклад 1