Dana jest tablica $a$ zawierająca $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$.
Należy odpowiedzieć na $q$ zapytań. W każdym zapytaniu dane są cztery liczby całkowite $\ell,r,u,v$ ($1\le\ell\le r\le n$, $1\le u\le v\le r-\ell+1$).
Rozważ podtablicę $a$ od indeksu $\ell$ do $r$, włącznie: $a_\ell,a_{\ell+1},\ldots,a_r$.
Niech $s=[s_1,s_2,\ldots,s_{r-\ell+1}]$ będzie tablicą uzyskaną przez posortowanie tej podtablicy niemalejąco. Nie zmieniamy kolejności żadnych elementów oryginalnej tablicy $a$, czyli po każdym zapytaniu tablica $a$ pozostaje taka sama.
Niech $t^{(i)}$ oznacza zbiór wartości występujących co najmniej $i$ razy w $s_u,s_{u+1},\ldots,s_v$.
Niech $f(t^{(i)})$ będzie bitowym OR wszystkich elementów $t^{(i)}$.
Wynik zapytania to $f(t^{(1)})+f(t^{(2)})+f(t^{(3)})$.
Na przykład niech $a=[123,3,2,2,7,2,1,5,5,7,456]$. Rozważmy zapytanie $\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$.
Wynik zapytania to $7+7+2=16$.
Wejście
Pierwszy wiersz wejścia zawiera $T$ ($1\le T\le2\cdot10^5$), liczbę przypadków testowych.
Następnie podanych jest $T$ przypadków testowych, każdy składający się z:
Pierwszego wiersza z dwiema liczbami całkowitymi $n$ i $q$ ($1\le n,q\le2\cdot10^5$).
Drugiego wiersza zawierającego dokładnie $n$ liczb całkowitych opisujących tablicę $a$ ($1\le a_i\le10^9$).
Następnych $q$ wierszy, z których każdy zawiera dokładnie cztery liczby całkowite $\ell,r,u,v$ ($1\le\ell\le r\le n$, $1\le u\le v\le r-\ell+1$).
Suma $n$ po wszystkich $T$ przypadkach testowych nie przekracza $2\cdot10^5$.
Suma $q$ po wszystkich $T$ przypadkach testowych nie przekracza $2\cdot10^5$.
Wyjście
Dla każdego przypadku testowego wypisz dokładnie $q$ wierszy. $i$-ty wiersz powinien zawierać dokładnie jedną liczbę całkowitą, odpowiedź na $i$-te zapytanie.
Przykład
Wejście 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
Wyjście 1
16 123 5