Homework#5987
Vasya studies at the Educational Institution of Economic Literacy (EIEL) and has received another homework task. But he has no time for such trivialities—he is on the verge of solving an NP-complete problem in polynomial time, which would upend the entire scientific community. In fact, he is close to resolving the maximum flow problem! Let's not distract Vasya with Edmonds, Dinics, and others—let's just help him complete his homework, since he has no time to waste.
The homework consists of a variant —a positive integer, and exercises. The condition of the -th exercise is given by a single integer x_i, which is coprime with . The answer to each exercise is the smallest positive integer such that x_iy \equiv 1 \pmod{m}. If such does not exist, output .
The first line contains two integers and (2 \le m \le 10^{14}, 1 \le q \le 2000), separated by a space. Each of the following lines contains a single integer x_i (1 \le x_i < m, x_i coprime with )—the condition for the -th exercise.
Print integers, one per line. The -th line must contain the answer to the -th exercise.
Example 1