P14933 [北大集训 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 补齐），定义如下三种运算： 1. **$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$)； 2. **$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$)； 3. **$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 \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$。 ### 【提示】 本题输入输出规模较大，请使用较为快速的输入输出方式。