Se te da un arreglo $a$ con $n$ enteros $a_1,a_2,\ldots,a_n$.
Debes responder $q$ consultas. En cada consulta se te dan cuatro enteros $\ell,r,u,v$ ($1\le\ell\le r\le n$, $1\le u\le v\le r-\ell+1$):
Considera el subarreglo de $a$ desde el índice $\ell$ hasta el índice $r$, ambos incluidos: $a_\ell,a_{\ell+1},\ldots,a_r$.
Sea $s=[s_1,s_2,\ldots,s_{r-\ell+1}]$ el arreglo obtenido al ordenar ese subarreglo de forma no decreciente. No cambiamos el orden de ningún elemento del arreglo original $a$; es decir, $a$ permanece igual después de cada consulta.
Sea $t^{(i)}$ el conjunto de valores que aparecen al menos $i$ veces en $s_u,s_{u+1},\ldots,s_v$.
Sea $f(t^{(i)})$ el OR bit a bit de todos los elementos de $t^{(i)}$.
El resultado de la consulta es $f(t^{(1)})+f(t^{(2)})+f(t^{(3)})$.
Por ejemplo, sea $a=[123,3,2,2,7,2,1,5,5,7,456]$. Considera la consulta $\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$.
El resultado de la consulta es $7+7+2=16$.
Entrada
La primera línea contiene $T$ ($1\le T\le2\cdot10^5$), el número de casos de prueba.
Siguen $T$ casos de prueba, cada uno formado por:
Una primera línea con dos enteros $n$ y $q$ ($1\le n,q\le2\cdot10^5$).
Una segunda línea con exactamente $n$ enteros que representan el arreglo $a$ ($1\le a_i\le10^9$).
Las siguientes $q$ líneas, cada una con exactamente cuatro enteros $\ell,r,u,v$ ($1\le\ell\le r\le n$, $1\le u\le v\le r-\ell+1$).
La suma de $n$ de los $T$ casos de prueba no supera $2\cdot10^5$.
La suma de $q$ de los $T$ casos de prueba no supera $2\cdot10^5$.
Salida
Para cada caso de prueba, muestra exactamente $q$ líneas. La línea $i$ debe contener exactamente un entero, la respuesta a la consulta $i$.
Ejemplos
Entrada 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
Salida 1
16 123 5