【北大集训2025】解开尘封的序列
给定进制数 $p \in \{2, 3\}$。定义 $p$ 进制下的位运算如下：
- 对于 $0 \le x < p^d$，设 $x$ 的 $p$ 进制表示为 $\overline{(x_{d-1} \cdots x_1 x_0)}_p$（不足 $d$ 位的用前导 0 补齐），定义 $\text{popcount}_p(x)$ 为 $x$ 的 $p$ 进制表示下非零位的个数，即 $\sum_{i=0}^{d-1} [x_i > 0]$。
- 对于 $0 \le x, y < p^d$，设 $x, y$ 的 $p$ 进制表示分别为 $\overline{(x_{d-1} \cdots x_1 x_0)}_p, \overline{(y_{d-1} \cdots y_1 y_0)}_p$（不足 $d$ 位的用前导 0 补齐），定义如下三种运算：
- $p$ 进制按位与：$x \text{ and}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = \min(x_i, y_i)$ ($0 \le i < d$)；
- $p$ 进制按位或：$x \text{ or}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = \max(x_i, y_i)$ ($0 \le i < d$)；
- $p$ 进制按位异或（即 $p$ 进制不进位加法）：$x \text{ xor}_p y = \overline{(z_{d-1} \cdots z_1 z_0)}_p$，其中 $z_i = (x_i + y_i) \bmod p$ ($0 \le i < d$)。
给定两个长度为 $n$ 的序列 $a, w$ 和一个长度为 $p^d$ 的序列 $z$，其中对于所有 $1 \le i \le n$，$0 \le a_i < p^d$。对于所有 $0 \le u < p^d$，定义 $u$ 的生成序列 $F(u)$ 如下：
对于 $1 \le i \le n$，令 $$ b_i = A \cdot \text{popcount}_p(a_i \text{ and}_p u) + B \cdot \text{popcount}_p(a_i \text{ or}_p u) + C \cdot \text{popcount}_p(a_i \text{ xor}_p u), $$ 其中 $A, B, C$ 为给定的非负整数。
令 $F(u)$ 为将 $b$ 从小到大排序后得到的序列，即 $F(u) = \text{sorted}([b_1, b_2, \dots, b_n])$。
有 $q$ 次询问，每次询问给定 $A, B, C, l_1, r_1, l_2, r_2$，求 $$ \left( \sum_{i=l_1}^{r_1} \sum_{j=l_2}^{r_2} z_i w_j F(i)_j \right) \bmod 2^{32}. $$
输入格式
从标准输入读入数据。
输入的第一行包含三个非负整数 $n, d, p$。
输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。
输入的第三行包含 $n$ 个非负整数 $w_1, w_2, \dots, w_n$。
输入的第四行包含 $p^d$ 个非负整数 $z_0, z_1, \dots, z_{p^d - 1}$。
输入的第五行包含一个正整数 $q$，表示询问次数。
输入的第 $i+5$ ($1 \le i \le q$) 行包含七个非负整数 $A, B, C, l_1, r_1, l_2, r_2$，表示第 $i$ 次询问。
输出格式
输出到标准输出。
输出 $q$ 行，第 $i$ ($1 \le i \le q$) 行一个非负整数表示第 $i$ 次询问的答案。
输入输出样例 #1
输入 #1
3 2 2 0 0 2 1 1 2 3 4 4 4 5 1 7 2 0 1 1 1 3 3 5 0 2 2 3 5 2 10 0 1 2 3 3 9 7 0 3 3 3 5 6 1 0 1 2 3
输出 #1
36 304 312 736 182
说明/提示
【子任务】
对于所有测试数据，均有：
- $1 \le n \le 3 \times 10^5$，$0 \le d \le 12$，$p \in \{2, 3\}$；
- 对于所有 $1 \le i \le n$，均有 $0 \le a_i < p^d$；
- 对于所有 $1 \le i \le n$，均有 $0 \le w_i < 2^{32}$；
- 对于所有 $0 \le i < p^d$，均有 $0 \le z_i < 2^{32}$；
- $1 \le q \le 3 \times 10^5$；
- $0 \le A, B, C \le 10^9$，$0 \le l_1 \le r_1 < p^d$，$1 \le l_2 \le r_2 \le n$。
| 子任务编号 | 分值 | $n \le$ | $d \le$ | $p =$ | $q \le$ | 特殊性质 |
|---|---|---|---|---|---|---|
| 1 | 5 | $5000$ | $12$ | $2$ | $5$ | 无 |
| 2 | 15 | $3 \times 10^5$ | $10$ | ^ | $10^5$ | 无 |
| 3 | 11 | ^ | $12$ | ^ | $3 \times 10^5$ | A |
| 4 | 8 | ^ | ^ | ^ | ^ | B |
| 5 | 17 | ^ | ^ | ^ | ^ | C |
| 6 | 17 | ^ | ^ | ^ | ^ | 无 |
| 7 | 11 | ^ | $5$ | $3$ | ^ | C |
| 8 | 16 | ^ | ^ | ^ | ^ | 无 |
特殊性质 A：所有询问的给出的三元组 $(A, B, C)$ 均相同。
特殊性质 B：对于所有询问，均有 $l_1 = r_1$。
特殊性质 C：对于所有询问，均有 $l_1 = 0$ 且 $r_1 = p^d - 1$。
【提示】
本题输入输出规模较大，请使用较为快速的输入输出方式。