Арифметичний прямокутник#5342
Після уроку з арифметичних прогресій вчитель дав Петру домашнє завдання: аркуш паперу з числами, записаними в деяких клітинках R \times C сітки. Деякі клітинки залишилися порожніми. Завдання Петра — створити арифметичний прямокутник, заповнивши відсутні числа. В арифметичному прямокутнику всі числа в кожному рядку та в кожному стовпці повинні утворювати арифметичну прогресію в порядку, в якому вони з'являються.
Наприклад, це арифметичний прямокутник:
1 3 5 7 9
2 2 2 2 2
3 1 -1 -3 -5
Петро занадто ледачий, щоб виконувати такі завдання вручну. Він хоче, щоб ви написали програму, яка зробить це за нього.
Вам надано сітку з цілих чисел, деякі з яких замінені крапками. З'ясуйте, чи можливо замінити крапки деякими раціональними числами, щоб отримати арифметичний прямокутник. Якщо є рішення, знайдіть одне.
Примітка: Арифметична прогресія — це послідовність чисел, така, що різниця будь-яких двох послідовних елементів послідовності є сталою.
Перший рядок вхідних даних містить два додатні цілі числа та : розміри сітки. Далі йдуть рядків, кожен з яких містить токенів, розділених одним пробілом. Кожен з токенів — це або крапка (.), або ціле число.
Обмеження
Кожне число, задане в сітці, знаходиться в межах від до включно. Є партій тестових випадків, кожна з яких коштує балів. У партіях з по маємо 1 \le R, C \le 6. Властивості окремих партій наведені нижче.
Партія 1. Усі числа вже заповнені.
Партія 2. Або R = 1, або C = 1 у кожному тестовому випадку.
Партія 3. R = C = 2 у кожному тестовому випадку.
Партія 4. Кожен тестовий випадок має унікальне рішення, яке можна знайти, використовуючи підхід, запропонований у першому прикладі.
Партія 5. Кожен тестовий випадок має унікальне рішення, і рішення містить лише цілі числа.
Партія 6. Кожен тестовий випадок має унікальне рішення.
Партія 7. Кожен тестовий випадок або має унікальне рішення, яке містить лише цілі числа, або не має рішення взагалі.
Партія 8. Кожен тестовий випадок або має унікальне рішення, або не має рішення взагалі.
Партія 9. Довільні тестові випадки.
Партія 10. Довільні тестові випадки з 1 \le R, C \le 50.
Якщо рішення немає, виведіть один рядок зі строкою "No solution." (лапки для ясності). Якщо є декілька рішень, виберіть і виведіть будь-яке одне рішення.
При виведенні рішення виведіть рядків, кожен з раціональними числами, розділеними пробілами.
Кожне раціональне число має бути надруковане як "N/D", де є додатнім, а і є взаємно простими. Якщо дорівнює , опустіть частину "/D".
Жодне число у вашому виведенні не може мати більше 20 цифр. (Це обмеження легко задовольнити, його єдина мета — спростити перевірку ваших виводів.)
Приклад 1