$k$ 阶 Thue-Morse 字符串是一个长度为 $2^k$ 的字符串，其中第 $i$ 个符号（从 $1$ 开始计数）若 $i-1$ 的二进制表示中 $1$ 的个数为偶数，则为 'A'，否则为 'B'。

长度为 $n$ 的字符串 $s$ 的后缀数组是一个从 $1$ 到 $n$ 的整数排列 $suf$，使得 $s[suf[1]..n], s[suf[2]..n], \dots, s[suf[n]..n]$ 是 $s$ 的所有非空后缀按字典序排序后的列表。

令 $suf$ 为 $k$ 阶 Thue-Morse 字符串的后缀数组。你的任务是计算 $q$ 个值：$suf[p_1], suf[p_2], \dots, suf[p_q]$。

输入格式

第一行包含两个整数 $k$ 和 $q$：Thue-Morse 字符串的阶数和查询次数（$0 \le k \le 60$，$1 \le q \le 10^5$）。

第二行包含 $q$ 个整数 $p_1, p_2, \dots, p_q$，用空格分隔：所需的索引（$1 \le p_i \le 2^k$）。

输出格式

输出 $q$ 个查询的答案，用空格分隔。

样例

输入 1

3 8
1 2 3 4 5 6 7 8

输出 1

6 7 4 1 8 5 3 2

说明

$3$ 阶 Thue-Morse 字符串为 “ABBABAAB”。