Hrvoje 最近学习了对数函数。他非常喜欢对于每一对正实数 $x$ 和 $y$ 都成立的性质 $\log(xy) = \log(x) + \log(y)$。

实际上，他并不关心函数本身，而是关心对数序列。长度为 $n$ 的对数序列是一个实数序列 $(a_1, a_2, \dots, a_n)$，对于每一对满足 $xy \le n$ 的正整数 $x$ 和 $y$，该序列都满足 $a_{xy} = a_x + a_y$。长度为 $6$ 的对数序列的一个例子是 $0, 1, \pi, 2, 0.7, 1 + \pi$。

为了完成作业，Hrvoje 需要写出 $q$ 个长度为 $n$ 的对数序列。然而，经过一整晚的努力，他醒来后发现 Matej 修改了每个序列中的恰好一个元素。Hrvoje 没有太多时间来修改他的作业，所以他想知道每个序列最少需要修改多少个元素才能使序列再次成为对数序列。不幸的是，Matej 是用钢笔写的，所以 Hrvoje 无法修改那个被 Matej 改过的元素。

Hrvoje 忘记了他为作业写的序列是什么，所以他只知道序列的数量 $q$、每个序列的长度 $n$ 以及第 $i$ 个序列中被 Matej 修改的元素的位置 $x_i$。

说明：可以证明，对于任何初始的对数序列，所需的最小修改次数都是相同的。

输入格式

第一行包含两个正整数 $n$ 和 $q$ ($1 \le n \le 10^8, 1 \le q \le 10^4$)，分别表示每个序列的长度和序列的数量。

接下来的 $q$ 行中，第 $i$ 行包含一个正整数 $x_i$ ($1 \le x_i \le n$)，表示第 $i$ 个序列中被 Matej 修改的元素的下标。

输出格式

在第 $i$ 行输出结果：如果 Hrvoje 无法通过修改第 $i$ 个序列中的其他元素使其再次成为对数序列，则输出 $-1$；否则，输出使序列再次成为对数序列所需的最小修改次数。

子任务

样例

样例输入 1

6 6
1
2
3
4
5
6

样例输出 1

-1
2
1
2
0
1

样例输入 2

20 5
7
8
2
19
12

样例输出 2

1
9
9
0
5

样例输入 3

10000 4
1234
2345
3456
7890

样例输出 3

15
148
3332
37

说明

第一个样例的解释： 如果初始序列是 $0, 1, \pi, 2, 0.7, 1 + \pi$，且 Matej 将第四个元素修改为 $8$，Hrvoje 可以将第二个元素修改为 $4$，将第六个元素修改为 $4 + \pi$，之后序列 $0, 4, \pi, 8, 0.7, 4 + \pi$ 将再次成为对数序列。