Задача A. Неправильный кабель ≡

Условие

Принтер соединен с компьютером кабелем, содержащим N линий данных, пронумерованных от 1 до N. Принтер имеет N контактов, также пронумерованных от 1 до N. При правильном подключении номер линии данных совпадает с номером контакта принтера (см. рис. 1).

По каждой линии данных i может передаваться сигнал s_i — "0" либо "1". При передаче в принтер кода символа по линиям 1, 2, ..., N одновременно передаются сигналы s₁, s₂, ..., s_N. Например, при N = 8 символу "A" может соответствовать код 01000001 — это значит, что по линиям с номерами 2 и 8 должен быть передан сигнал "1", а по остальным — сигнал "0" (см. рис. 1).

В результате неправильного монтажа кабеля линии могли быть соединены не с теми контактами принтера. Известно, что линии не соединены между собой и не оборваны. На рис. 2 изображен пример неправильного монтажа кабеля при N = 8.

Схему монтажа кабеля можно обозначить перестановкой π₁π₂, … , π_N чисел от 1 до N, где π_i - номер линии, подсоединенной к i-му контакту принтера. Например, правильному монтажу, изображенному на рис. 1, соответствует перестановка 1 2 3 4 5 6 7 8, а неправильному монтажу, изображенному на рис. 2, — перестановка 1 2 5 3 4 6 8 7.

При передаче кода s₁, s₂, … , s_N по кабелю принтер получит код , который может отличаться от исходного из-за ошибок монтажа. Например, при передаче кода 01001101 по кабелю на рис. 2 принтер получит код 01100110. Заметим, что код 11000100 здесь будет передан правильно.

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

Даны M пар кодов. Код состоит из N символов, каждый из которых либо "0", либо "1". Первым в паре стоит код, переданный с компьютера, вторым — код, полученный принтером. Программа должна однозначно определить схему монтажа кабеля (перестановку чисел от 1 до N), либо сообщить, что это невозможно.

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 10000.

Примеры тестов

8 3
11110000 11110000
11001100 11001010
10101010 10101001

1 2 3 4 5 8 6 7

Задача B. Свинья-копилка ≡

Условие

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

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Формат входного файла

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — C_i W_i. Все числа во входном файле — целые.

Формат выходного файла

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число −1.

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

Примеры тестов

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1

Задача C. Связка брусков ≡

Условие

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

По длинам сторон сечения каждого бруска a₁ b₁ и a₂ b₂ определить минимальную длину веревки.

Формат входного файла

Во входном файле содержатся вещественные положительные числа a₁ b₁ a₂ b₂.

Формат выходного файла

Выходной файл должен содержать одно вещественное число с точностью до 2 знаков после запятой — минимальную длину веревки.

Примеры тестов

3 1 1 1

8.83

Задача D. Последняя цифра ≡

Условие

Дано N целых чисел a₁, a₂, … , a_N. Требуется найти две последние цифры числа, определяющего количество натуральных делителей произведения a₁ × a₂ × … × a_N. Если число делителей меньше 10, то вывести это число без лидирующего нуля.

Формат входного файла

В первой строке входного файла содержится число N. В следующей строке содержатся числа a₁, a₂, … , a_N.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 20; 1 ≤ a_i ≤ 10000

Примеры тестов

4
3 5 7 720

20

4
64 1024 9 5

02

3
2 3 5

8