RoAlgo PreOJI 2024 VIII | matmare

Task

You are given two sequences, $a$ of size $n$ and $b$ of size $m$, both indexed from $1$. A matrix $mat$ of $n$ rows and $m$ columns is constructed where $mat_{i, j} = a_i | b_j$. The operation $x | y$ for natural numbers $x$ and $y$ refers to the bitwise OR operation. The operation is performed as follows: the numbers $x$ and $y$ are written in base $2$, and the number $x | y$ has bit $i$ active if and only if either $x$ has the respective bit active or $y$ has the respective bit active.

You are given $q$ queries of the form: given a submatrix, calculate the sum of the values in it.

Note: In C++, the bitwise OR operation can be implemented as "$x | y$".

Input data

The input is read from the file matmare.in. The first line contains $n$, $m$, $q$. The second line contains the sequence $a$ of $n$ elements. The third line contains the sequence $b$ of $m$ elements.

The next $q$ lines each contain four values $l$, $c$, $x$, $y$, representing a query about the submatrix between rows $l$ and $x$ and columns $c$ and $y$.

Output data

The output will be written to the file matmare.out. It will contain $q$ lines, each containing a single number: the sum of the submatrix for the $i$-th query.

Constraints and clarifications

• $0 \leq a_i, b_i < 2^{26}$
• $n, m, q \leq 200\,000$

Example

matmare.in

3 4 2
1 4 3
4 6 1 0
1 1 3 4
1 2 3 3

matmare.out

53
29

Explanation

The resulting matrix is as follows:

5 7 1 1
4 6 5 4
7 7 3 3

For the first query, the sum of the elements in the entire matrix is $5+7+1+1+4+6+5+4+7+7+3+3 = 53$.

For the second query, the sum of the elements in the submatrix $(1,2),(3,3)$ is $7+1+6+5+7+3 = 29$.