Фирма Macrohard разработала новый протокол обмена данными по сети. Каждый блок данных при этом обмене состоит из \(N\) чисел в диапазоне от 0 до \(M\)-1 включительно. Чтобы повысить надежность передачи, вместе с блоком данных пересылается контрольный блок такой же длины.

Предположим, что исходный блок состоит из чисел \(a_1\), \(a_2\),…,\(a_N\). Тогда, контрольный блок состоит из чисел \(b_1\), \(b_2\),…,\(b_N\), из диапазона от 0 до \(M\)-1 включительно таких, что выполняются следующие равенства: \(b_1\) = (\(a_N\) + \(b_N\)) mod \(M\), \(b_2\) = (\(a_1\) + \(b_1\)) mod \(M\), ... , \(b_N\) = (\(a_N\)-1 + \(b_N\)-1) mod \(M\) (обозначение \(X\) mod \(M\) обозначает остаток от деления \(X\) на \(M\), например, 7 mod 4 = 3, 6 mod 2 = 0).

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

Ваня хочет поступить на работу программистом в фирму Macrohard, и в качестве вступительного задания ему поручили написать процедуру построения контрольного блока для заданного блока данных. Помогите ему!

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно \(K\) различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием \(K\). А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 - так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам \(N\) и \(K\) найдет количество нулей в конце записи в системе счисления с основанием \(K\) числа \(N\)!=1·2·3·...·(\(N\)-1)·\(N\), чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

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

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел \(i\)-й строки за \(H_i\), а сумму чисел \(j\)-го столбца за \(V_j\). Упорядоченный набор чисел (\(H_1\), \(H_2\), …, \(H_N\), \(V_1\), \(V_2\), …, \(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.

Строительная компания хочет построить дом, в котором будет \(n\) квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как \(a_1\), \(a_2\), …, \(a_n\).

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных \(i\) и \(j\) должны выполняться условия: \(a_i\) не делится на \(a_j\), а \(a_i\)² делится на \(a_j\).

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 2⁶³ – 1.

2

6523157998489532400
5519595229491142800