Problem E
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 subarray 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 subarray in nondecreasing 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 