Santa and Reindeer

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, Brain****, C, C++, Clang, Clang++, COBOL, Coffee, D, Fortran, Go, Haskell, Java, JS, Kotlin, LOLCODE, Lua, Mono C#, Mono F#, NASM, NASM64, OCaml, Pascal, Perl, PHP, Processing, Python, Racket, Ruby, Rust, Sed, TCL, Text, Turing

After a long day at work, Santa comes home only to discover that his newborn reindeer have been numbered wrong by Mrs. Clause.

Normally, the N baby reindeer would be numbered 1, 2, ..., N. However, Mrs. Clause has absentmindedly numbered the ith reindeer the value of the ith prime number instead.

Santa is tired, so he wants you to deal with the logistic problems that arise with this new numbering. His assistant will ask you Q questions. The ith question will ask you for the regular number of the reindeer with the current number a_i. You must find the value of this regular number or that no reindeer is labeled the given number.

Input Specification

The first line will contain two space-separated integers, N and Q (1 \le N, Q \le 2 \cdot 10^5).

The next Q lines will each contain one integer, a_i (1 \le a_i \le 2 \cdot 10^6).

Output Specification

For each question, output the regular number of the reindeer in question on a separate line. If there is no reindeer with that number, output -1 instead.


Subtask 1 [30%]

1 \le N \le 10^4

Subtask 2 [70%]

No further constraints.

Sample Input

5 4

Sample Output


Explanation for Sample Output

2 is the first prime number, so its regular number is 1.

5 and 11 are the third and fifth prime numbers respectively, so their regular numbers are 3 and 5.

20 is not a prime number, so it has no regular number attached to it.


There are no comments at the moment.