Given a base $p \in \{2, 3\}$. Define the bitwise operations in base $p$ as follows: For $0 \le x < p^d$, let the base-$p$ representation of $x$ be $(x_{d-1} \dots x_1 x_0)_p$ (padded with leading zeros to $d$ digits). Define $\text{popcount}_p(x)$ as the number of non-zero digits in the base-$p$ representation of $x$, i.e., $\sum_{i=0}^{d-1} [x_i > 0]$. For $0 \le x, y < p^d$, let the base-$p$ representations of $x$ and $y$ be $(x_{d-1} \dots x_1 x_0)_p$ and $(y_{d-1} \dots y_1 y_0)_p$ respectively (padded with leading zeros to $d$ digits). Define the following three operations: 1. $p$-ary bitwise AND: $x \text{ and}_p y = (z_{d-1} \dots z_1 z_0)_p$, where $z_i = \min(x_i, y_i)$ ($0 \le i < d$); 2. $p$-ary bitwise OR: $x \text{ or}_p y = (z_{d-1} \dots z_1 z_0)_p$, where $z_i = \max(x_i, y_i)$ ($0 \le i < d$); 3. $p$-ary bitwise XOR (i.e., $p$-ary addition without carry): $x \text{ xor}_p y = (z_{d-1} \dots z_1 z_0)_p$, where $z_i = (x_i + y_i) \pmod p$ ($0 \le i < d$).

Given two sequences $a$ and $w$ of length $n$, and a sequence $z$ of length $p^d$, where $0 \le a_i < p^d$ for all $1 \le i \le n$. For all $0 \le u < p^d$, define the generated sequence $F(u)$ as follows: For $1 \le i \le n$, let $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)$, where $A, B, C$ are given non-negative integers. Let $F(u)$ be the sequence obtained by sorting $b$ in non-decreasing order, i.e., $F(u) = \text{sorted}([b_1, b_2, \dots, b_n])$.

There are $q$ queries. Each query provides $A, B, C, l_1, r_1, l_2, r_2$. Calculate $$\left( \sum_{i=l_1}^{r_1} \sum_{j=l_2}^{r_2} z_i w_j F(i)_j \right) \pmod{2^{32}}$$

Input

• The first line contains three non-negative integers $n, d, p$.
• The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$.
• The third line contains $n$ non-negative integers $w_1, w_2, \dots, w_n$.
• The fourth line contains $p^d$ non-negative integers $z_0, z_1, \dots, z_{p^d-1}$.
• The fifth line contains a positive integer $q$, representing the number of queries.
• The $i+5$-th line ($1 \le i \le q$) contains seven non-negative integers $A, B, C, l_1, r_1, l_2, r_2$, representing the $i$-th query.

Output

• Output $q$ lines. The $i$-th line ($1 \le i \le q$) contains a non-negative integer representing the answer to the $i$-th query.

Constraints

• $1 \le n \le 3 \times 10^5$, $0 \le d \le 12$, $p \in \{2, 3\}$;
• For all $1 \le i \le n$, $0 \le a_i < p^d$;
• For all $1 \le i \le n$, $0 \le w_i < 2^{32}$;
• For all $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$.

Subtasks

• Special Property A: All given triples $(A, B, C)$ in the queries are identical.
• Special Property B: For all queries, $l_1 = r_1$.
• Special Property C: For all queries, $l_1 = 0$ and $r_1 = p^d - 1$.

Note

The input and output scale for this problem is large; please use efficient input and output methods.