eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Домашнє завдання

Домашнє завдання

Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB

Вася навчається у Освітньому Закладі Економічної Грамоти (ОЗЕГ) і йому задали чергове домашнє завдання. Але йому ніколи займатись такими дурницями, він майже наблизився до розв'язання однієї NP-повної задачі за поліноміальний час, чим переверне усю наукову спільноту. Йому майже вдалось розв'язати задачу про максимальний потік! Тільки давайте не будемо розстроювати Васю усілякими Едмонсами, Дініцами та іншими, а просто допоможемо зробити домашнє завдання, адже у нього немає часу.

Завдання складається з варіанта m — цілого додатнього числа, та q вправ. Умова i-ї вправи складається з єдиного цілого числа x_i, взаємно-простого з m. Відповіддю до вправи є мінімальне ціле додатнє число таке, що залишок від ділення числа на m дорівнює 1. Якщо такого числа не існує, то відповіддю є -1.

Вхідні дані

У першому рядку записані через пропуск два цілих числа m та q (2m10^14, 1q2000). У i-му з q наступних рядків міститься єдине число x_i (1x_{i }< m, x_i взаємно-просте з m) — умова i-ї вправи.

Вихідні дані

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

Приклад

Вхідні дані #1
5 4
1
2
3
4
Вихідні дані #1
1
4
4
2
Автор Олег Петров
Джерело Літня школа Севастополь 2013, Хвиля 2, День 6