Вася учится в Образовательном Учреждении Экономической Грамоты (ОУЭГ) и ему задали очередное домашнее задание. Но ему некогда заниматься такой ерундой, он вплотную приблизился к решению одной \textbf{NP}-полной задачи за полиномиальное время, чем перевернёт всё научное сообщество. Ему почти удалось решить задачу о максимальном потоке! Только давайте не будем расстраивать Васю всякими Эдмонсами, Диницами и прочими, а просто поможем сделать домашнее задание, у него ведь нет времени. \includegraphics{https://static.e-olymp.com/content/69/69c560e78c9833e7e04be32b7574dee73cafe616.jpg} \includegraphics{https://static.e-olymp.com/content/93/93d7577dcc3dcb613ca49ee20b56b2cfb6494dd1.jpg} Задание состоит из варианта \textbf{m} --- целого положительного числа, и \textbf{q} упражнений. Условие \textbf{i}-го упражнения состоит из единственного целого числа \textbf{x_i}, взаимно-простого с \textbf{m}. Ответом на упражнение является минимальное целое положительное число такое, что остаток от деления числа на \textbf{m} равен \textbf{1}. Если такого числа не существует, то ответом является \textbf{-1}. \InputFile В первой строке записаны через пробел два целых числа \textbf{m} и \textbf{q} (\textbf{2} ≤ \textbf{m} ≤ \textbf{10^14}, \textbf{1} ≤ \textbf{q} ≤ \textbf{2000}). В \textbf{i}-й из \textbf{q}следующих строк содержится единственное число \textbf{x_i} (\textbf{1} ≤ \textbf{x}_\{i \}< \textbf{m}, \textbf{x_i} взаимно-просто с \textbf{m}) --- условие \textbf{i}-го упражнения. \OutputFile Выведете \textbf{q} целых чисел, каждое в отдельной строке. \textbf{i}-я строка должна содержать ответ на \textbf{i}-е упражнение.