题目描述

对于一个用恰好 $N$ 位二进制表示的正整数 $x$，定义操作 $\operatorname{trim}(x)$：删除其二进制表示左侧和右侧连续的 $0$，但保留中间的 $0$。

例如，当 $N=6$ 时：

• $x=4=000100_2$，则 $\operatorname{trim}(4)=1_2$；
• $x=10=001010_2$，则 $\operatorname{trim}(10)=101_2=5$。

现在考虑所有整数 $1,2,\ldots,2^N-1$，它们均用恰好 $N$ 位二进制表示。对每个数执行 $\operatorname{trim}$ 操作后，将得到的数按如下规则排序：

1. 先按二进制表示中 $1$ 的个数从小到大排序；
2. 若 $1$ 的个数相同，则按 $\operatorname{trim}$ 后的数值从小到大排序。

最后，将排序后的所有数的二进制表示依次拼接成一个长二进制串，位置从左到右编号为 $1$。

给定 $N$ 以及 $T$ 个询问位置 $p_1,p_2,\ldots,p_T$，请回答拼接串中这些位置上的比特值。

输入格式

第一行包含两个整数 $N,T$。

第二行包含 $T$ 个整数：

输出格式

输出一个长度为 $T$ 的 01 串，不含空格。第 $i$ 个字符表示位置 $p_i$ 上的比特。

数据范围

• $1\le N\le 100$；
• $2\le T\le 100000$；
• $1\le p_i\le 10^{18}$；
• 保证所有 $p_i$ 不超过最终拼接串的长度。

子任务

样例

样例 1

3 10
7 1 2 3 4 5 6 8 9 10

1111111101

当 $N=3$ 时，初始数为 $1$ 到 $7$。执行 trim 并排序后得到：

1_2, 1_2, 1_2, 11_2, 11_2, 101_2, 111_2

拼接串为 1111111101111。

样例 2

5 10
1 2 3 4 15 23 19 45 66 99

1111011111