AT_abc425_g [ABC425G] Sum of Min of XOR

You are given positive integers $ N,M $ and a sequence of non-negative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Find $ \displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right) $ . Here, $ x\oplus A_i $ represents the bitwise $ \mathrm{XOR} $ of $ x $ and $ A_i $ . What is bitwise $ \mathrm{XOR} $ operation? The bitwise $ \mathrm{XOR} $ of non-negative integers $ X,Y $ , $ X \oplus Y $ , is defined as follows: - When $ X \oplus Y $ is written in binary, the digit in the $ 2^k $ ( $ k \geq 0 $ ) place is $ 1 $ if exactly one of $ X,Y $ has $ 1 $ in the $ 2^k $ place when written in binary, and $ 0 $ otherwise. For example, $ 3 \oplus 5 = 6 $ (in binary representation: $ 011 \oplus 101 = 110 $ ).

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answer.

### Sample Explanation 1 - When $ x=0 $ : $ x\oplus A_1=1,x\oplus A_2= 2 $ , so $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1 $ . - When $ x=1 $ : $ x\oplus A_1=0,x\oplus A_2= 3 $ , so $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0 $ . - When $ x=2 $ : $ x\oplus A_1=3,x\oplus A_2= 0 $ , so $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0 $ . - When $ x=3 $ : $ x\oplus A_1=2,x\oplus A_2= 1 $ , so $ \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1 $ . Therefore, output $ 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 $ - All input values are integers.