Задача A. Функция Эйлера - 1 ≡

Условие

Необходимо вычислить функцию Эйлера для натурального числа N.

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

Входной файл содержит одно целое положительное число N.

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

Выходной файл должен содержать одно целое положительно число - значение функции Эйлера для N.

Ограничения

1 ≤ N ≤ 10⁷

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

5

4

9

6

Задача B. Система вычетов ≡

Условие

Заданы модуль M и количество операций по этому модулю N.

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

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

Входной файл содержит в первой строке натуральное число M, во второй строке число N, в последующих N строк содержатся операции в формате "5+5", где вместо "+" могут быть так же "-" и "*", а числа не менее нуля и не более тысячи.

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

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

Ограничения

2 ≤ M ≤ 1000

0 ≤ N ≤ 1000

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

7
3
5+4
4-5
3*4

0 1 2 3 4 5 6 
1 2 3 4 5 6 
1 3 6 3 6 2 
3 5 
2
6
5

Задача C. Код Хэмминга ≡

Условие

Необходимо реализовать код Хэмминга с размером информационного блока в M бит.

Входной файл содержит M, текст, который нужно закодировать и последовательность бит, которая была закодирована данным кодом, и которую необходимо декодировать. Текст может содержать только символы ASCII 32−122. Каждый символ кодируется 1 байтом. В случае, если в последнем информационном блоке остались лишние биты, они берутся за 0.

В закодированной последовательности не может быть более одной ошибки на каждый M+K блок бит. Размер контрольного блока K необходимо определить автоматически с наименьшей возможной избыточностью. Длина текста не более 10000 символов, длина закодированной последовательности не более 100000 символов.

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

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

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

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

Ограничения

1 ≤ M ≤ 1000

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

2
Star
10011100111001101111100111110000000100111001101111000001110010011011110000001111

10011100110000001111100110111110011000001001111100000001001110011011110000011100
Wars

7
Hello !
1100101001110100111001000010101010010000011000000110011010111101010010011101000111000101

0001100110001000111001000010101010010000011011111000011100111111001110000000001011001001
Welcome