AT_arc217_d [ARC217D] Greedy Customer

正整数 $ N,M $ と長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 正整数 $ k $ に対し、 $ f(k) $ を以下の問題の答えとして定義します。 > 高橋君はお金を $ k $ 円持っています。また、AtCoder 商店には $ N $ 個の品物があり、 $ i $ 番目の品物は $ A_i $ 円です。 > > 高橋君は、 $ i=1,2,\ldots,N $ の順に以下の行動を行います。 > > - 今持っているお金が $ A_i $ 円以上ならば $ i $ 番目の品物を購入する。 > > 高橋君が買った品物の値段の合計を求めてください。 $ \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)) $ を求めてください。ただし、 $ \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)) $ は $ 1\times f(1), 2\times f(2), \ldots, M\times f(M) $ のビット単位 $ \mathrm{XOR} $ として定義されます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 ビット単位 $ \mathrm{XOR} $ 演算とは 非負整数 $ A, B $ のビット単位 $ \mathrm{XOR} $ 、 $ A \oplus B $ は、以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると： $ 011 \oplus 101 = 110 $ )。 一般に $ k $ 個の非負整数 $ p_1, p_2, p_3, \dots, p_k $ のビット単位 $ \mathrm{XOR} $ は $ (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) $ と定義され、これは $ p_1, p_2, p_3, \dots, p_k $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 例えば高橋君の最初の所持金が $ 3 $ 円の場合、高橋君は以下のように行動します。 - $ i=1 $ のとき：高橋君の所持金は $ 3 $ 円であり、 $ 2 $ 円以上なので $ 1 $ 番目の品物を買う。 - $ i=2 $ のとき：高橋君の所持金は $ 1 $ 円であり、 $ 3 $ 円以上ではないので $ 2 $ 番目の品物を買わない。 - $ i=3 $ のとき：高橋君の所持金は $ 1 $ 円であり、 $ 1 $ 円以上なので $ 3 $ 番目の品物を買う。 これより $ f(3)=2+1=3 $ が分かります。 $ f(1),f(2),f(3),f(4),f(5),f(6) $ の値はそれぞれ $ 1,2,3,3,5,6 $ です。したがって、 $ 1,4,9,12,25,36 $ のビット単位 $ \mathrm{XOR} $ である $ 61 $ が答えになります。 ### Constraints - $ 1\le T \le 10 $ - $ 1\le N,M $ - 全てのテストケースにおける $ N $ の総和は $ 5\times 10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 5\times 10^7 $ 以下 - $ 1\le A_i \le M $ - 入力される値は全て整数