eolymp
bolt
Try our new interface for solving problems
Problems

Домашнее задание

Домашнее задание

Time limit 3 seconds
Memory limit 256 MiB

Вася учится в Образовательном Учреждении Экономической Грамоты (ОУЭГ) и ему задали очередное домашнее задание. Но ему некогда заниматься такой ерундой, он вплотную приблизился к решению одной NP-полной задачи за полиномиальное время, чем перевернёт всё научное сообщество. Ему почти удалось решить задачу о максимальном потоке! Только давайте не будем расстраивать Васю всякими Эдмонсами, Диницами и прочими, а просто поможем сделать домашнее задание, у него ведь нет времени.

Задание состоит из варианта m — целого положительного числа, и q упражнений. Условие i-го упражнения состоит из единственного целого числа x_i, взаимно-простого с m. Ответом на упражнение является минимальное целое положительное число такое, что остаток от деления числа на m равен 1. Если такого числа не существует, то ответом является -1.

Input data

В первой строке записаны через пробел два целых числа m и q (2m10^14, 1q2000). В i-й из qследующих строк содержится единственное число x_i (1x_{i }< m, x_i взаимно-просто с m) — условие i-го упражнения.

Output data

Выведете q целых чисел, каждое в отдельной строке. i-я строка должна содержать ответ на i-е упражнение.

Examples

Input example #1
5 4
1
2
3
4
Output example #1
1
4
4
2
Author Олег Петров
Source Летняя школа Севастополь 2013, Волна 2, День 6