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.