该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

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

Format

Input

第一行包含两个正整数n($\le 10^8$)、q($\le 10^6$)，分别表示输出结果的范围和查询的个数。

接下来q行每行一个正整数k，表示查询第k小的素数。

Output

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

Samples

100 5
1
2
3
4
5

2
3
5
7
11

Limitation

1s, 1024KiB for each test case.