$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)}$의 모든 원소에 비트 OR 연산을 적용한 값이라 하자.
질의의 결과는 $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$).
둘째 줄에는 배열 $a$를 나타내는 정확히 $n$개의 정수가 주어진다 ($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