Домашнє завдання
Вася навчається у Освітньому Закладі Економічної Грамоти (ОЗЕГ) і йому задали чергове домашнє завдання. Але йому ніколи займатись такими дурницями, він майже наблизився до розв'язання однієї 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-ту вправу.