Задача 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