P3383 [Template] Linear Sieve for Primes

This problem has been updated: it now asks for querying the $k$-th smallest prime instead of primality testing. Hint: The input/output and computation workload can be large. - For C++: if you use `cin` for I/O, consider `std::ios::sync_with_stdio(0)` for acceleration, and use `'\n'` for newlines. - For Java: using a linear sieve with optimized I/O can pass within the time limit, though it may be tight. - For Python: performance varies widely by implementation; using arrays from the `numpy` library instead of lists, together with the Sieve of Eratosthenes, can still pass within reasonable time and memory limits.

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

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 $q$ lines, each containing a single integer as the answer.

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