VZLA2019C - Challenge Accepted!

Little Rubdary has been training a lot for the Mathematics and Informatics Olympiads. She has been studying divisibility, and has come with a new problem for you!

Is there a positive number that is divisible by the first N natural numbers? If so, can you find the smallest one?
Can you find the answer to Q values of N?

You gladly accept this challenge, but with one condition: as the answers may be extremely large, you will show them modulo some number M

Input

The first line contains two integer Q and M, which specify the number of questions to be answered and the modulo respectively. Then, will follow the descriptions of the Q questions.

Output

For each question you must print the answer to the challenge modulo M in a single line. In case there is no answer to the question, you must output -1

Example

Input:
5 990901
1
6
12
20
60 Output: 1
60
27720
921726
823252

Constraints

1 ≤ Q ≤ 103
1 ≤ N ≤ 3*105
2 ≤ M ≤ 109


Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Samuel Nacache - Used for Venezuelan 2019 ICPC Local Contest

hide comments
2019-11-03 05:34:00
Hey is M a prime??
Can you check my solution and tell me if im missing any case! 24757129
2019-10-28 14:22:55
Copy of SMALL / SMALLM. Please delete.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.