Problem J
Easy Query
You are given an array $a$ with $n$ integers $a_{1}, a_{2}, \ldots , a_{n}$.
You need to answer $q$ queries. In each query, you are given $4$ integers $\ell $, $r$, $u$ and $v$ $(1 \le \ell \le r \le n, 1 \le u \le v \le r-\ell +1)$:
-
Consider the sub-array of $a$ from index $\ell $ to index $r$, inclusive: $a_{\ell }, a_{\ell +1}, \ldots , a_{r}$.
-
Let $s = [s_{1}, s_{2}, \ldots , s_{r-\ell +1}]$ be the array obtained by sorting the above sub-array in non-decreasing order. Please note that we do not change the order of any elements in the original array $a$, i.e. array $a$ remains the same after every query.
-
Let $t^{(i)}$ be the set of values which appears at least $i$ times in $s_{u}, s_{u+1}, \ldots , s_{v}$.
-
Let $f(t^{(i)})$ be the bitwise OR of all elements in $t^{(i)}$.
-
The result of the query is $f(t^{(1)}) + f(t^{(2)}) + f(t^{(3)})$.
For example, let $a = [123, 3, 2, 2, 7, 2, 1, 5, 5, 7, 456]$. Consider the query with $\ell = 2, r = 10, u = 2, v = 8$:
-
$s = [1, 2, 2, 2, 3, 5, 5, 7, 7]$.
-
$t^{(1)} = \{ 2, 3, 5, 7\} $.
-
$t^{(2)} = \{ 2, 5\} $.
-
$t^{(3)} = \{ 2\} $.
-
$f(t^{(1)}) = 2 \mathbin {|} 3 \mathbin {|} 5 \mathbin {|} 7 = 7$.
-
$f(t^{(2)}) = 2 \mathbin {|} 5 = 7$.
-
$f(t^{(3)}) = 2$.
-
Result of the query is $7 + 7 + 2 = 16$.
Input
The first line of input contains $T$ $(1 \leq T \leq 2 \cdot 10^5)$ — the number of test cases.
$T$ test cases follow, each consists of:
-
The first line contains $2$ integers $n$ and $q$ $(1 \le n, q \le 2 \cdot 10^{5})$.
-
The second line contains exactly $n$ integers, representing array $a$ $(1 \le a_{i} \le 10^{9})$.
-
In the next $q$ lines, each line contains exactly $4$ integers $\ell $, $r$, $u$ and $v$ $(1 \le \ell \le r \le n, 1 \le u \le v \le r-\ell +1)$.
The sum of $n$ over all $T$ test cases does not exceed $2 \cdot 10^5$.
The sum of $q$ over all $T$ test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output exactly $q$ lines, the $i$-th line contains exactly one integer — the answer to the $i$-th query.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 11 3 123 3 2 2 7 2 1 5 5 7 456 2 10 2 8 1 1 1 1 1 4 1 3 |
16 123 5 |
