$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