K-th Smallest Prime Query

Given an integer n representing the range [1, n] and an integer q representing the number of queries, answer each query by outputting the k-th smallest prime number in the range.

For example, if n = 10, then the primes in the range are [2, 3, 5, 7]. A query with k = 3 will output 5.

Note: It is guaranteed that for every query, the k-th prime exists within the given range.

inputFormat

The first line contains two integers n and q separated by a space.

The next q lines each contain an integer k, representing a query that asks for the k-th smallest prime number.

outputFormat

Output exactly q lines. Each line should contain the answer to the corresponding query, which is the k-th smallest prime number in the range [1, n].

sample

10 3
1
2
3

2
3
5