### 问题描述 小然是一名充满魔法的舞者，他的舞蹈动作都以二进制的形式存在。在他的世界中，每一个二进制位都代表了一种特别的舞姿。他擅长的是一种名为 "二进制矩阵之舞" 的舞蹈，他需要在舞台上表演一系列由二进制数构成的动作。 在一次表演中，小然将会获得一个二进制数组 $A$，由 $N$ 个元素组成。然后，他需要处理 $Q$ 个查询，每个查询都以一种特殊的形式出现： 每个查询包含五个整数 $k, L_1, R_1, L_2, R_2$。可以保证 $1 \leq L_1 \leq R_1 < L_2 \leq R_2$。查询的答案是满足以下条件的 $(i,j)$ 对的数量： - $L_1 \leq i \leq R_1$ 且 $L_2 \leq j \leq R_2$。 - $A_i ⊕ A_j$ 的第 $k$ 个比特位为 $1$。其中 $\oplus$ 表示位异或运算。 请帮助小然计算每个查询的答案，让他能够成功完成这场舞蹈。 ### 输入格式 - 第一行包含一个单独的整数 $T$，表示测试用例的数量。 - 每个测试用例包含多行输入： - 测试用例的第一行包含两个空格隔开的整数 $N$ 和 $Q$，分别表示数组中的元素数量和查询的数量。 - 测试用例的第二行包含 $N$ 个空格隔开的整数 $A_1, A_2, ..., A_N$。 - 接下来的 $Q$ 行描述查询，每行包含五个空格隔开的整数 $k, L_1, R_1, L_2, R_2$，即查询的参数。 ### 输出格式 对于每个测试用例，输出 $Q$ 行。每行应该是对应查询的答案。 ### 输入样例 ```markdown 2 5 2 1 2 4 3 2 1 1 3 5 5 2 1 2 3 5 6 2 3 5 6 13 12 20 1 1 4 5 6 3 2 3 4 6 ``` ### 输出样例 ```markdown 2 2 4 4 ``` ### 说明 考虑第一个测试用例: 数组为 $A = [1, 2, 4, 3, 2]$。 - 第一个查询: 范围是 $[1, 3]$ 和 $[5, 5]$，$k = 1$。有三对 $(i, j)$：$(1, 5)$，$(2, 5)$，$(3, 5)$。对于 $A_i ⊕ A_j$，只有 $(1, 5)$ 和 $(3, 5)$ 的第 $k$ 个比特位为 1，因此答案为 2。 - 第二个查询: 范围是 $[1, 2]$ 和 $[3, 5]$，$k = 2$。有六对 $(i, j)$，满足条件的有 $(1, 3)$ 和 $(2, 3)$，因此答案为 $2$。 ### 评测数据规模 $1 \leq T \leq 1 \times 10^3$。 $2 \leq N \leq 10^5$。 $1 \leq Q \leq 5 \times 10^5$。 $0 \leq A_i < 2^{60}$。 $1 \leq L_1 \leq R_1 < L_2 \leq R_2 \leq N$。 $0 \leq k < 60$。 所有测试用例中 $N$ 和 $Q$ 的和不会超过 $10^5$ 和 $5 \times 10^5$。