Алгоритмы

В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T₁ минуту поезд идет со скоростью V₁ метр в минуту, потом T₂ минуты со скоростью V₂ метра в минуту, ..., наконец, T_N минут со скоростью V_N метрв в минуту. При этом на любом из этих участков поезд может стоять (V_i = 0).

По действующей инструкции обеспечения безопасности движения расстояние между началами двух следующих друг за другом поездов не должно превышать L метров. Напишите программу, которая по этим данным определяет минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться без опасного сближения.

Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T_i и V_i (1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000).

Выходные данные
Требуется вывести минимально допустимый интервал отправления поездов в минутах, с не менее, чем тремя знаками после точки.

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

Для уменьшения конкуренции театры хотят разместиться в домах на этой улице так, чтобы минимальное расстояние между двумя соседними театрами было как можно больше.

Входные данные

Первая строка входных данных содержит  количество домов на улице N и количество театров K (1 ≤ K ≤ N ≤ 104). Далее идет N чисел в порядке возрастания  – координаты домов на улице.

Выходные данные

Выведите единственное число  – наибольшее возможное допустимое расстояние между театрами.

N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.

Требуется определить, за какое наименьшее количество взрывов можно уничтожить все корабли, а также в какие моменты времени и в каких точках для этого следует произвести взрывы. Время отсчитывается от момента, когда координаты движущихся кораблей были определены со спутника.

Входные данные
В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 10⁵. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.

Выходные данные
В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.

Если решений несколько, выведите любое из них.

В программе Microsoft Excel имеется возможность сортировки таблицы по значениям какого-нибудь столбца. В процессе сортировки переставляются целиком строки таблицы (а не только значения в столбце, по которому осуществляется сортировка). При этом используется устойчивая сортировка, то есть если в этом столбце в нескольких строках стоят одинаковые значения, то эти строки после сортировки будут расположены в том же порядке, что и до сортировки (т.е. раньше будет идти та строка, которая до сортировки шла раньше).

Вася последовательно сортировал всю таблицу несколько раз. Вам дана последовательность номеров столбцов, по которым Вася сортировал таблицу — в этой последовательности один и тот же столбец мог встречаться несколько раз, например, если Вася отсортировал ее сначала по 1-му столбцу, потом по 2-му, а затем снова по 1-му.

Вам требуется написать программу, которая определит, можно ли было как-то оптимизировать последовательность сортировок так, чтобы результат не изменился (независимо от содержания таблицы). Например, если последовательность состоит из двух сортировок по столбцу 1, то можно оставить только одну такую сортировку.

Входные данные
В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 10⁶).  Во второй строке содержатся N натуральных чисел, не превосходящих 10⁵ – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.

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

Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество ресурсов.

Ваша задача - помочь бедному Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.

Задача слегка упрощается тем, что замок Короля представляет собой многоугольник и расположен на плоской поверхности. Архитектор уже сопоставил замку прямоугольную декартову систему координат и точно определил координаты каждого угла замка в футах.



Входные данные
Первая строка содержит два целых числа N и L, разделённых пробелом: N - число углов в замке Короля, а L - минимальное число футов, на которое Король разрешил приблизить стену к замку.

Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа x_i и y_i, разделённых пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.

Ограничения: 3 <= N <= 1000, 1 <= L <= 1000, -10 000 <= x_i, y_i <= 10 000.

Выходные данные
Выводится единственное число - минимальная длина стены в футах, которая может быть построена вокруг замка согласно требованиям Короля. Вы должны представить Королю целое число футов, потому что вещественные числа ещё не изобретены. Однако результат нужно округлить так, чтобы он отличался не более чем на 8 дюймов от правильного (1 фут = 12 дюймов), потому что большей неточности Король не потерпит.

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

• Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.

Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.

Ограничения: длина исходной последовательности от 1 до 100.

Входные данные
В первой строке находится последовательность символов от A до Z.

Выходные данные
В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.

Выходные данные
Выводится искомая последовательность скобок без пробелов.

Примеры

№	Входные данные	Выходные данные
1	([(]	()[()]
2	(	()

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x₁, y₁), а вторая - в точке (x₂, y₂).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L₁, L₂, ..., L_K и количество отрезков каждой длины C₁, C₂, ..., C_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 <= K <= 4, 1 <= x₁, y₁, x₂, y₂, L_i <= 1000, 1 <= C_i <= 10, все числа целые.



Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, K, затем 2_K чисел: L₁, L₂, ..., L_K, C₁, C₂, ..., C_K.

Выходные данные
Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

Выходные данные
В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

Входные данные
В первой строке находятся числа a₁ и N, разделённые пробелом.

Выходные данные
Вывести одно число - a_N.

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников).

Входные данные
В первой строке содержится число прямоугольников N. Далее идут N строк, содержащих по 4 числа x₁, y₁, x₂, y₂ - координаты двух противоположных углов прямоугольника.

Ограничения: 1 <= N <= 100, координаты представляют собой целые числа и по абсолютной величине не превосходят 10 000.

Выходные данные
Вывести одно число - количество частей, на которые разбивается плоскость.

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

Входные данные
В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.

Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.

Выходные данные
Вывести одно число - максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение "AA", нужно нажать

(ABC)(пауза)(ABC)

Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырёх нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.



Входные данные
В первой строке задана длина оригинального сообщения N. Вторая строка содержит полученное SMS-сообщение. 1 <= N <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

Выходные данные
Вывести число сообщений из N букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.

Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

Недавно он получил по электронной почте фотографию места преступления. Подозрительный фрагмент (тот, на котором изображен предмет, похожий на шахматную доску) уже был скопирован в отдельный файл, но вдруг выяснилось, что, поскольку фотография была сжата с потерей качества, некоторые пиксели на ней из белых или черных стали серыми. Таким образом, определение того, является ли сфотографированный предмет шахматной доской, стало намного более сложным.

Все усложняется тем, что на фотографию могла попасть не вся шахматная доска, а лишь ее часть. Например, на приведенном рисунке на фотографию попала часть доски, у которой каждое поле имеет длину стороны, равную трем пикселям.

Помогите частному сыщику в расследовании преступления. Напишите программу, которая определит, может ли заданный фрагмент фотографии быть изображением части шахматной доски, и, если может, восстановит изображение шахматной доски до сжатия.

Шахматная доска — это квадрат, разбитый на \(x^2\) (для некоторого \(x\)) равных квадратов — полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет — черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

Формат входных данных
Первая строка содержит два целых числа: \(m\) и \(n\) — размеры фрагмента фотографии в пикселях (\(1 \le m, n \le 250\)).

Следующие \(m\) строк содержат по \(n\) символов каждая, \(j\)-й символ \(i\)-й строки соответствует пикселю с координатами \((i, j)\). Символ <<.>> (точка) означает белый пиксель, символ <<*>> — черный, символ <<?>> — серый.

Формат выходных данных
Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите слово <<YES>>. После этого выведите \(m\) строк по \(n\) символов в каждой. Они должны содержать изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае выведите слово <<NO>>.

Зал супермаркета имеет форму прямоугольника размером M x N, в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером K  x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.




Входные данные
В первой строке вводятся три натуральных числа M, N и K (M, N ≤ 100, K ≤ M). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число V – количество витрин (0 ≤ V ≤ N*M). В следующих V строках входных данных содержатся различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до M–1) – расстояние от левой стены супермаркета до витрины, второе (от 0 до N–1) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

Выходные данные
В первой строке выведите минимальное количество витрин, которые необходимо убрать. Во второй строке выведите возможный маршрут передвижения супервитрины: одну строку из заглавных латинских букв, обозначающих следующее:

U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.
Количество символов в строке не должно превышать N x M
.

Если возможных маршрутов несколько, то выведите любой из них.

Крупная межгалактическая сеть мебельных магазинов Galactic-Мебель недавно вышла на рынок мебели для кухонь в звездной системе LoST-2007. В этой звездной системе во всех квартирах кухни имеют форму прямоугольника размером a на b метров. При этом вдоль одной из стен принято ставить стол, в смежной с ней стене находится окно. Таким образом, для размещения различных кухонных шкафчиков остается угол со сторонами a и b метров.

Для экономии места в этой звездной системе принято ставить шкафчики вплотную друг к другу и к углу кухни. Кроме этого, сами шкафчики встраиваются внутрь стены, то есть вдоль стены расположены только их дверцы.

В звездной системе LoST-2007 используется n типов кухонных шкафчиков. Каждый тип шкафчиков характеризуется своей шириной wi, при этом на кухне должен присутствовать ровно один экземпляр каждого типа шкафчиков.

Недавно директор маркетингового отдела Galactic-Мебель заметил, что он может предложить клиентам несколько вариантов расположения шкафчиков на кухне. Различными считаются варианты, которые отличаются расположением хотя бы одного шкафчика. При этом шкафчики различных типов могут иметь одинаковую ширину, однако отличаются внешней отделкой. Так что даже размещения, которые отличаются лишь позициями шкафчиков с равной шириной, считаются различными. Например, пусть a = 3, b = 4 и есть два типа шкафчиков, шириной 1 и 2, соответственно.


Тогда возможно шесть планировок кухни. Возможные планировки показаны на рисунке.

Требуется по заданным размерам кухни и шкафчиков найти число различных планировок.

Входные данные
Первая строка содержит три целых числа: a, b и n (1 ≤ a ≤ 300, 1 ≤ b ≤ 300, 1 ≤ n ≤ 100). Каждая из следующих n строк содержит целое число w_i (1 ≤ w_i ≤ 300) — ширину соответствующего шкафчика.

Выходные данные
Выведите количество различных планировок кухни.

На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты n окопов. Каждый окоп вырыт вдоль границы прямоугольника со сторонами, параллельными направлениям север–юг и запад–восток. При этом окопы могут иметь общие точки, но никакие два окопа не имеют общего участка ненулевой длины.

Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.

Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

Формат входных данных

Первая строка содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₁ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

Формат выходных данных

Выведите одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^-6.

Вася нарисовал выпуклый N-угольник и провел в нем несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри N-угольника. Теперь он утверждает, что весь N-угольник оказался разбит на треугольники. Напишите программу, которая проверяет истинность Васиного утверждения.

Входные данные
Сначала вводятся числа N - количество вершин N-угольника (3 <= N <= 1000) и M - количество диагоналей, проведенных Васей. Далее на вход программы поступают M пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри N-угольника. Вершины N-угольника нумеруются числами от 1 до N.

Выходные данные
Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число K - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено K чисел - номера вершин исходного N-угольника, которые являются вершинами этой K-угольной части в порядке обхода этой части.

Рассмотрим таблицу, состоящую из N строк и M столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу p, если все числа в ее ячейках кратны p.

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел i-й строки за Hi, а сумму чисел j-го столбца за Vj. Упорядоченный набор чисел (H₁, H₂, …, H_N, V₁, V₂, …, V_M) назовем профилем матрицы. Скажем, что матрица почти кратна p, если все числа, входящие в ее профиль, кратны p. Почти кратная 5 матрица и ее профиль изображены на рисунке 1.


Если две матрицы A и B имеют одинаковый размер, причем элемент, стоящий на пересечении i-й строки и j
-го столбца в матрице A отличается от соответствующего элемента матрицы B не более чем на p, скажем, что A отличается от B не более чем на p. Скажем, что матрица B похожа на матрицу A относительно числа p, если

1. отличается от не более чем на p
2. профили B и A совпадают.

На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но непохожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

Входные данные
В первой строке входных данных задаются целые числа p (1 <= p <= 10), N и M (1 <= N, M <= 30). Следующие N строк содержат по M целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы A.

Выходные данные
Выведите матрицу B по строкам - сначала M элементов первой строки, затем M элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.