Арифметический Прямоугольник
После урока по арифметическим прогрессиям учитель дал Петру домашнее задание: лист бумаги с числами, записанными в некоторых ячейках R×C сетки. Некоторые ячейки остались пустыми. Задача Петра — создать арифметический прямоугольник, заполнив недостающие числа. В таком прямоугольнике все числа в каждом ряду и в каждом столбце должны образовывать арифметическую прогрессию в порядке их появления.
Например, это арифметический прямоугольник:
1 3 5 7 9
2 2 2 2 2
3 1 -1 -3 -5
Петру не хочется выполнять такие задания вручную. Он хочет, чтобы вы написали программу, которая сделает это за него.
Вам дана сетка из целых чисел, некоторые из которых заменены точками. Определите, возможно ли заменить точки на некоторые рациональные числа, чтобы получить арифметический прямоугольник. Если решение существует, найдите его.
Примечание: Арифметическая прогрессия — это последовательность чисел, такая, что разность любых двух последовательных элементов последовательности является постоянной.
Входные данные
Первая строка входных данных содержит два положительных целых числа R и C: размеры сетки. Далее следуют R строк, каждая из которых содержит C токенов, разделенных одним пробелом. Каждый из токенов — это либо точка (.), либо целое число.
Ограничения
Каждое число, данное в сетке, находится в диапазоне от -100 до 100 включительно. Существует 10 наборов тестов, каждый из которых стоит 10 баллов. В наборах 1 до 9 мы имеем 1 ≤ R, C ≤ 6. Свойства отдельных наборов приведены ниже.
Набор 1. Все числа уже заполнены.
Набор 2. Либо R = 1, либо C = 1 в каждом тестовом случае.
Набор 3. R = C = 2 в каждом тестовом случае.
Набор 4. Каждый тестовый случай имеет уникальное решение, которое можно найти, используя подход, предложенный в первом примере.
Набор 5. Каждый тестовый случай имеет уникальное решение, и решение содержит только целые числа.
Набор 6. Каждый тестовый случай имеет уникальное решение.
Набор 7. Каждый тестовый случай либо имеет уникальное решение, содержащее только целые числа, либо не имеет решения вообще.
Набор 8. Каждый тестовый случай либо имеет уникальное решение, либо не имеет решения вообще.
Набор 9. Произвольные тестовые случаи.
Набор 10. Произвольные тестовые случаи с 1 ≤ R, C ≤ 50.
Выходные данные
Если решения нет, выведите одну строку с текстом "No solution." (кавычки для ясности). Если существует несколько решений, выберите и выведите любое одно решение.
При выводе решения выведите R строк, каждая из которых содержит C разделенных пробелами рациональных чисел.
Каждое рациональное число должно быть напечатано в виде "N/D", где D положительно, а N и D взаимно просты. Если D равно 1, опустите часть "/D".
Ни одно число в вашем выводе не должно содержать более 20 цифр. (Это ограничение легко удовлетворить, его единственное назначение — упростить проверку ваших выводов.)