AT_abc425_g [ABC425G] Sum of Min of XOR

正整数 $ N,M $ と長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ \displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right) $ を求めてください。 ただし、 $ x\oplus A_i $ は $ x $ と $ A_i $ のビット単位 $ \mathrm{XOR} $ を表します。 ビット単位 $ \mathrm{XOR} $ 演算とは 非負整数 $ X,Y $ のビット単位 $ \mathrm{XOR} $ 、 $ X \oplus Y $ は、以下のように定義されます。 - $ X \oplus Y $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ X,Y $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101 = 110 $ )。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 - $ x=0 $ のとき： $ x\oplus A_1=1,x\oplus A_2= 2 $ なので $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1 $ です。 - $ x=1 $ のとき： $ x\oplus A_1=0,x\oplus A_2= 3 $ なので $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0 $ です。 - $ x=2 $ のとき： $ x\oplus A_1=3,x\oplus A_2= 0 $ なので $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0 $ です。 - $ x=3 $ のとき： $ x\oplus A_1=2,x\oplus A_2= 1 $ なので $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1 $ です。 したがって、 $ 1+0+0+1=2 $ を出力してください。 ### Constraints - $ 1\le N\le 2\times 10^5 $ - $ 1\le M\le 10^9 $ - $ 0\le A_i \le 10^9 $ - 入力される値は全て整数