#P1105. 2023.03.21-第六题-二叉树染色(Ⅱ)

2023.03.21-第六题-二叉树染色(Ⅱ)

题目内容

塔子哥是一个热爱编程的大学生,他喜欢参加各种算法竞赛,挑战自己的智力。有一天,他在网上看到了一个有趣的二叉树问题,他决定尝试一下。他用纸和笔画出了一个 nn 层的满二叉树(共 2n12^n-1 个节点,编号从 112n12^n-1 ,对于编号为 ii1i2n111 \le i\le 2^{n-1} -1 )的节点,它的左儿子为 2i2*i ,它的右儿子为 2i+12*i+1),然后用红色的笔操作 qq 次,每次都是在某些节点上画圈,表示将这些节点及其子树染红。他想知道每次染红后,二叉树中有多少个红色的节点。

他觉得这个问题很简单,只要用递归或者栈就可以解决。但是,当他开始编写代码时,他发现问题并没有那么容易。他需要考虑很多细节,比如如何存储和更新二叉树的状态,如何避免重复计算,如何优化时间和空间复杂度等等。他越写越觉得头疼,越写越觉得不对劲。他开始怀疑自己的能力,甚至怀疑这个问题是否有解。他不甘心放弃,他决定向你求助,希望你能给他一些提示或者思路。你能帮助塔子哥吗?

输入描述

第一行输入两个正整数 nnqq ,代表二叉树的层数和操作次数。

接下来的 qq 行,每行输入一个正整数 aia_i ,代表染色的节点编号。

1n401\le n \le 40

1q100001 \le q \le 10000

1ai2n1 \le a_i \le 2^n

输出描述

输出 qq 行,每行输入一个正整数,代表当前操作结束后二叉树的红色节点数量。

样例

输入

4 2
4
3

输出

3
10