签到题(counting)

题目描述

两位神仙 zzh 和 cjz 在玩游戏。

这个游戏中有 $2^n$ 个点，这些点依次编号为 $0,1,2,..,2^n-1$，每个点有一个权值 $v_i$ 。

zzh 和 cjz 可以在这些点间移动，但两人的移动方式不同。

如果 zzh 当前在点 $i$ ，她下一步可以移动到点 $i-1$ 或者点 $i+1$(如果这些点存在)，因此，zzh 从点 $i$ 移动到点 $j$ 需要的最少步数为 $|i-j|$。

cjz 会使用更加神仙的移动方式，如果他当前在点 $i$ ，则他下一步可以移动到 $j$ 当且仅当 $j\in\{0,1,2,...,2^n-1\}$ 且 $bitcount(i\oplus j)=1$ ，这里 $\oplus$ 表示按位异或，即C++中的 i^j，而 $bitcount(x)$ 表示非负整数 $x$ 的二进制表示中 $1$ 的个数。

可以发现，cjz 从点 $i$ 移动到点 $j$ 需要的最少步数为 $bitcount(i\oplus j)$ 。

现在 zzh 和 cjz 会进行 $m$ 次操作，每次操作中他们会给出三个非负整数 $x,p,q$ ，满足 $x\leq 2^n-1,p\leq 2^n-1,q\leq n$ 。此时称一个点 $y$ 是好的，当且仅当 zzh 能从 $x$ 出发在 $p$ 步内到达 $y$ ，且 cjz 能从 $x$ 出发在 $q$ 步内到达 $y$。即，满足 $y\in\{0,1,2,...,2^n-1\},|x-y|\leq p,bitcount(x\oplus y)\leq q$

对于每次操作， zzh 和 cjz 会求出所有合法的点的权值和，即：

$$\sum_{y\in\{0,1,2,...,2^n-1\},|x-y|\leq p,bitcount(x\oplus y)\leq q} v_y $$

现在他们希望你也对于每次操作求出这个值。

输入格式

从文件 counting.in 读入。

输入第一行包含两个正整数 $n,m$ ，含义见题面。

输入第二行包含 $2^n$ 个正整数 $v_0,v_1,...,v_{2^n-1}$ ，依次表示每个点的点权。

接下来 $m$ 行，第 $i$ 行包含三个非负整数 $x_i,p_i,q_i$ ，表示第 $i$ 个操作中给出的参数。

输出格式

输出到文件 counting.out。

输出 $m$ 行，第 $i$ 行一个数表示第 $i$ 个操作的答案。

样例

样例输入1

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

样例输出1

15
13
13

样例解释1

三组询问中满足要求的 $y$ 分别为：

$$\{2,4,5,6\}\\ \{4,6,7\}\\ \{2,3,4\}$$

样例输入/输出 2~7

见下发文件

样例 $1\sim 7$ 依次满足测试点 $2,2,2,5,8,12,16$ 的限制。

数据范围与限制

对于所有数据，保证 $n\leq 18,m\leq 5\times 10^5,v_i\leq 10^9$ 。

对于所有编号为奇数的测试点，额外保证 $m\leq 10^5$。

测试点编号	特殊限制
$1$	$m=0$
$2,3,4$	$n\leq 10,m\leq 2000$
$5,6,7$	$q_i=n$
$8,9,10,11$	$x_i=0$
$12,13,14,15$	$p_i=2^n-1$
$16,17,18,19,20$	无特殊限制

友情提示：LL不规范，爆零两行泪。

本题需要输入/输出优化