Cerință

Se dau două șiruri, $a$ de mărime $n$ și $b$ de mărime $m$, ambele indexate de la $1$. Se construiește matricea $mat$ de $n$ linii și $m$ coloane, unde $mat_{i, j}$ = $a_i | b_j$. Prin operația $x$ | $y$, pentru $x$ și $y$ numere naturale, ne referim la operația de SAU pe biti. Operația se efectuează astfel: se scriu numerele $x$ și $y$ în baza $2$, iar numărul $x$ | $y$ are bitul $i$ activ dacă și numai dacă fie $x$ are bitul respectiv activ, fie $y$ are bitul respectiv activ.

Se dau $q$ intrebari de forma: dându-se o submatrice, calculați suma valorilor din aceasta.

$\bold{Notă}$: in C++, operatia de SAU pe biti se poate implementa astfel: "$x | y$".

Date de intrare

Se citesc $n$, $m$, $q$ pe prima linie din fișierul de intrare matmare.in. Pe a doua linie se citește șirul $a$ de $n$ elemente. Pe a treia linie se citește sirul $b$ de $m$ elemente.

Pe următoarele $q$ linii se citesc patru valori $l$, $c$, $x$, $y$, semnificând o intrebare despre submatricea dintre liniile $l$ și $x$ și coloanele $c$ și $y$.

Date de ieșire

Se vor afișa $q$ linii, pe a $i$-a fiind un singur număr: suma submatricei de la întrebarea $i$.

Restricții și precizări

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

Exemplu

matmare.in

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

matmare.out

53
29

Explicație

Matricea rezultată este următoarea:

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

Pentru prima întrebare, suma elementelor din întreaga matrice este $5+7+1+1+4+6+5+4+7+7+3+3 = 53$.

Pentru a doua întrebare, suma elementelor din submatricea $(1,2),(3,3)$ este $7+1+6+5+7+3 = 29$.