Домашнее задание
Вася учится в Образовательном Учреждении Экономической Грамоты (ОУЭГ) и ему задали очередное домашнее задание. Но ему некогда заниматься такой ерундой, он вплотную приблизился к решению одной NP-полной задачи за полиномиальное время, чем перевернёт всё научное сообщество. Ему почти удалось решить задачу о максимальном потоке! Только давайте не будем расстраивать Васю всякими Эдмонсами, Диницами и прочими, а просто поможем сделать домашнее задание, у него ведь нет времени.
Задание состоит из варианта m — целого положительного числа, и q упражнений. Условие i-го упражнения состоит из единственного целого числа x_i, взаимно-простого с m. Ответом на упражнение является минимальное целое положительное число такое, что остаток от деления числа на m равен 1. Если такого числа не существует, то ответом является -1.
Входные данные
В первой строке записаны через пробел два целых числа m и q (2 ≤ m ≤ 10^14, 1 ≤ q ≤ 2000). В i-й из qследующих строк содержится единственное число x_i (1 ≤ x_{i }< m, x_i взаимно-просто с m) — условие i-го упражнения.
Выходные данные
Выведете q целых чисел, каждое в отдельной строке. i-я строка должна содержать ответ на i-е упражнение.