Домашнє завдання#5987
Вася навчається у Освітньому Закладі Економічної Грамоти (ОЗЕГ) і отримав чергове домашнє завдання. Але у нього немає часу займатися такими дурницями — він майже розв'язав одну з NP-повних задач за поліноміальний час, що сколихне наукову спільноту. Він майже вирішив задачу про максимальний потік! Давайте не відволікатимемо Васю Едмонсами, Дініцями та іншими алгоритмами, а просто допоможемо йому виконати домашнє завдання, адже часу у нього обмаль.
Завдання складається з варіанту — додатного цілого числа, та вправ. Умова -ї вправи – одне число x_i, яке є взаємно простим з . Відповідь до вправи — найменше додатне ціле число таке, що x_iy \equiv 1 \pmod{m}. Якщо такого не існує, надрукуйте -1.
У першому рядку записано два цілих числа і (2 \le m \le 10^{14}, 1 \le q \le 2000) через пробіл. У кожному з наступних рядків одне число x_i (1 \le x_i < m, x_i взаємно просте з ) — умова -ї вправи.
Виведіть цілих чисел — по одному в кожному рядку. -й рядок має містити відповідь до -ї вправи.
Приклад 1