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