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 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.

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