Description

Given an upper bound $n$ and $q$ queries, for each query output the $k$-th smallest prime number.

Input Format

The first line contains two positive integers $n, q$, representing the query range and the number of queries.

Each of the next $q$ lines contains a positive integer $k$, asking for the $k$-th smallest prime.

Output Format

Output $q$ lines, each containing a single integer as the answer.

100 5
1
2
3
4
5

2
3
5
7
11

Hint

Constraints
For $100\%$ of the testdata, $n = 10^8$, $1 \le q \le 10^6$, and it is guaranteed that the requested primes do not exceed $n$.

Data by NaCly_Fish.

Translated by ChatGPT 5