Homework
Vasya is a student at the Educational Institution of Economic Literacy (EIEL) and has been assigned another homework task. However, he is preoccupied with a groundbreaking attempt to solve an NP-complete problem in polynomial time, which could transform the scientific world. He is close to cracking the maximum flow problem! To spare Vasya from dealing with complex algorithms like Edmonds and Dinic, let's assist him with his homework, as he is pressed for time.
The homework involves a variant m — a positive integer, and q exercises. Each exercise i is defined by a single integer x_i, which is coprime with m. The solution to each exercise is the smallest positive integer whose remainder when divided by m is 1. If no such integer exists, the answer should be -1.
Input
The first line contains two integers m and q (2 ≤ m ≤ 10^14, 1 ≤ q ≤ 2000), separated by a space. Each of the following q lines contains a single integer x_i (1 ≤ x_{i }< m, x_i coprime with m), representing the condition for the i-th exercise.
Output
Print q integers, each on a new line. The i-th line should display the answer to the i-th exercise.