题目描述

给定长度为n的“对数序列”定义：序列(a₁, …, aₙ)满足对所有正整数x, y且xy ≤ n有aₓᵧ = aₓ + aᵧ。

现在有q个修改操作，原本都是对数序列的序列，但每个序列恰好在位置xᵢ的元素被任意改动过（只改了这一处）。已知对于任意初始对数序列，固定被动的位置后，使序列在不改动该位置的前提下，回复为某个对数序列所需的最小改动数。注意只依赖于位置xᵢ（与具体原序列无关）。

输入格式

• 第一行：两个正整数n和q（1 ≤ n ≤ 10⁸，1 ≤ q ≤ 10⁴），分别表示序列长度和序列个数。

• 接下来 q 行：每行一个正整数 xᵢ（1 ≤ xᵢ ≤ n），表示第 i 个序列中被修改的元素的下标。

输出格式

对于每个查询，如果无法通过修改其他元素使序列重新变为对数序列，则输出 -1。否则，输出使序列重新变为对数序列所需的最小修改次数。

样例输入

6 6 1 2 3 4 5 6

输出

-1 2 1 2 0 1

样例 1 说明

如果初始序列是 0, 1, π, 2, 0.7, 1+π。可以将第二个元素修改为 4，第六个元素修改为 4+π，并且将第四个元素修改为 8，那么 4+π 将重新变为对数序列。