给定一个包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 的数组 $a$。
你需要回答 $q$ 次询问。每次询问给出四个整数 $\ell,r,u,v$（$1\le\ell\le r\le n$，$1\le u\le v\le r-\ell+1$）：
考虑数组 $a$ 下标从 $\ell$ 到 $r$（含两端）的子数组：$a_\ell,a_{\ell+1},\ldots,a_r$。
设 $s=[s_1,s_2,\ldots,s_{r-\ell+1}]$ 为将上述子数组按非递减顺序排序后得到的数组。注意，我们不会改变原数组 $a$ 中任何元素的顺序，即每次询问后数组 $a$ 保持不变。
设 $t^{(i)}$ 为在 $s_u,s_{u+1},\ldots,s_v$ 中至少出现 $i$ 次的值组成的集合。
设 $f(t^{(i)})$ 为集合 $t^{(i)}$ 中所有元素的按位或。
询问结果为 $f(t^{(1)})+f(t^{(2)})+f(t^{(3)})$。
例如，设 $a=[123,3,2,2,7,2,1,5,5,7,456]$。考虑 $\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$.
询问结果为 $7+7+2=16$。
输入格式
输入第一行包含 $T$（$1\le T\le2\cdot10^5$），表示测试用例的数量。
接下来有 $T$ 个测试用例，每个包含：
第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le2\cdot10^5$）。
第二行恰好包含 $n$ 个整数，表示数组 $a$（$1\le a_i\le10^9$）。
接下来 $q$ 行，每行恰好包含四个整数 $\ell,r,u,v$（$1\le\ell\le r\le n$，$1\le u\le v\le r-\ell+1$）。
所有 $T$ 个测试用例的 $n$ 之和不超过 $2\cdot10^5$。
所有 $T$ 个测试用例的 $q$ 之和不超过 $2\cdot10^5$。
输出格式
对于每个测试用例，恰好输出 $q$ 行，第 $i$ 行恰好包含一个整数，表示第 $i$ 次询问的答案。
样例
输入格式 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
输出格式 1
16 123 5