题目背景

春天的美好季节，一定要出去踏青！

题目描述

zxh 准备去踏青。

一开始，zxh 不知道任何景点。zxh 总共会搜索 $q$ 次，每次搜索到一个景点。每个景点用一个 $n$ 位的二进制数 $a_i$ 表示它包含哪些景色，$a_i$ 可以是 $0$。（输入时使用十进制）

zxh 会安排若干次踏青，每次踏青是依次访问若干个景点（可以重复访问同一个景点）。

在一次踏青中，如果连续访问的两个景点 $u$ 和 $v$ 满足 $a_u \;\text{or}\; a_v = 2^n - 1$（即它们按位或的结果包含了所有 $n$ 种景色），那么这次踏青就是“不值得期待”的。

zxh 不会安排不值得期待的踏青。因此，一次踏青中相邻的两个景点必须满足 $a_u \;\text{or}\; a_v \neq 2^n - 1$。

在每一次搜索之后（也就是得到了前 $k$ 个景点之后），zxh 想知道：至少需要安排几次踏青，才能把当前已经搜索到的所有景点都至少访问一次。

注意，不同的踏青之间没有顺序要求，每次踏青可以独立选择景点序列。

你需要对每次搜索后，输出这个最少踏青次数。

输入格式

第一行，两个整数 $n,q$。

接下来 $q$ 行，每行一个数 $a_i$ 表示搜索到的景点。

输出格式

共 $q$ 行，每行一个整数，表示插入后的答案。

3 4
3
5
1
6

1
2
1
2

提示

对于第四次询问，获得 $a_i=6$ 的新景点后，$3 \to 1 \to 5$，形成一次踏青；$6$ 独自形成一次踏青（注意单独的一个景点也可以是一次踏青），答案为 $2$。

---

::cute-table{tuack}

Subtask 编号	$q\le$	特殊性质	分值
#1	$15$	无	$2$
#2	$10^3$	^	$7$
#3	$10^5$		$23$
#4	$5 \times 10^5$	A	$15$
#5	^	无	$53$

特殊性质 A：$n \le 2$。

对于 $100\%$ 的数据，$1 \le n \le 60,0 \le a_i \le 2^n-1,1 \le q \le 5 \times 10^5$。