1. Квадрат Рубика

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: square.in
Вихідний файл: square.out
Програма: square.*

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

Комірки квадратної таблиці по 2n комірок у кожному рядку й по 2n комірок у кожному стовпчику, заповнено натуральними числами, що не перевищують 100. За один крок дозволено дзеркально відобразити («перегорнути») довільний рядок або стовпчик таблиці. Далі подано кілька прикладів здійснення такої операції: ліворуч подано початкове заповнення таблиці, а праворуч три таблиці — приклади заповнення таблиці після здійснення одного з можливих ходів. Виділено рядок або стовпчик, що було дзеркально відображено.

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

можна перетворити до потрібного вигляду за 4 кроки (виділено рядки та стовпчики, над якими було здійснено операцію на попередньому кроці):

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

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

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

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

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

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

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

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

Приклад

2. Гнізда

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: nests.in
Вихідний файл: nests.out
Програма: nests.*

На вертикальній стіні будинку N сімей ластівок побудували свої гнізда таким чином, що жодні два гнізда не розташовані на одній вертикалі або горизонталі. Нещодавно ластівки вирішили підключити до Інтернету кожне з гнізд. Для цього у ластівки, що живе найвище, розмістили супутникову антену. Усім ластівкам, що живуть нижче, Інтернет підключать через гнізда, розташовані вище.

Технологія підключення Інтернету така. Від найвищого гнізда проводять 2 кабелі: один до найвищого гнізда ліворуч від даного і один до найвищого гнізда праворуч. Після цього дві множини гнізд (ліворуч і праворуч від найвищого) розглядаються абсолютно незалежно. Для обох частин проводиться підключення без урахування протилежної частини. Звісно, якщо в одній з частин немає гнізд, то кабель в цю сторону не протягують. Відстань між точками (x₁; y₁) та (x₂; y₂) вважається рівною |x₂ – x₁| + |y₂ – y₁|.

Завдання
Визначте найменшу загальну довжину кабелю, який потрібно придбати для підключення усіх гнізд. Розмірами гнізд знехтувати (вважайте їх точками). Розв’язання за O(N) набирає 100%, за O(N ln N) — 75%, за O(N²) — 30% балів.

Вхідні дані
Перший рядок містить натуральне число N. Наступні N рядків містять прямокутні цілі координати гнізда (x;y). Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000. Гнізда подано у порядку збільшення їхніх абсцис x.

Тести
У всіх тестах N ≤ 250 000. У 30% тестів N ≤ 3 000, а у 75% тестів N ≤ 125 000.

Вихідні дані
Єдиний рядок файлу містить шукану найменшу загальну цілу довжину кабелю. Відповідь на всі тести не перевищує 10¹⁸.

Зауваження для учасників, що використовують С++
В цій задачі можливі дуже великі вхідні данні, тому не радимо користуватись модулем iostream для введення даних. Також printf() та fprintf() неправильно виводить числа типу long long.

Приклад

nests.in	nests.out	ілюстрація
9 0 8 1 7 2 4 3 9 4 5 5 6 6 2 7 3 8 1	27