题目描述

给定进制数 $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$ 次询问的答案。

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

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						无
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$。

【提示】

本题输入输出规模较大，请使用较为快速的输入输出方式。