【模板】线性筛素数

题目背景

本题已更新,从判断素数改为了查询第 $k$ 小的素数 提示:如果你使用 `cin` 来读入,建议使用 `std::ios::sync_with_stdio(0)` 来加速。

题目描述

如题,给定一个范围 $n$,有 $q$ 个询问,每次输出第 $k$ 小的素数。

输入输出格式

输入格式


第一行包含两个正整数 $n,q$,分别表示查询的范围和查询的个数。 接下来 $q$ 行每行一个正整数 $k$,表示查询第 $k$ 小的素数。

输出格式


输出 $q$ 行,每行一个正整数表示答案。

输入输出样例

输入样例 #1

100 5
1
2
3
4
5

输出样例 #1

2
3
5
7
11

说明

【数据范围】 对于 $100\%$ 的数据,$n = 10^8$,$1 \le q \le 10^6$,保证查询的素数不大于 $n$。 Data by NaCly\_Fish.