Problem Statement

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$).

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.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N

Output

Output the answer.