Exam

Execution time limit is 1 second

Runtime memory usage limit is 256 megabytes

After consuming a large volume of compote, people lose the ability to count properly. This is exactly what happened to our hero. He was sure that he had earned enough points for the semester to be able to pass the exam. Unfortunately, he was wrong. He is now only one problem away from passing the exam, but the exam is tomorrow. Help him solve this problem.

You are given an array $a$ consisting of $n$ integers and an integer $k$ . We say that an array $b$ with $t$ elements is good if popcount $(b_{1} ∣ b_{2} ∣ \dots b_{t - 1} ∣ b_{t}) \geq k$ , where $∣$ denotes bitwise OR and popcount( $x$ ) returns the number of ones in the binary representation of $x$ . The imbalance of an array $b$ is defined as max(b) - min(b), where max and min denote the maximum and the minimum elements of array $b$ , respectively.

Find the minimum imbalance among all good subsequences of the array $a$ . If there is no such subsequence, print "-1".

The bitwise OR between two numbers $a$ and $b$ is defined for each bit separately. If the $i$ -th bit in $a$ is equal to $1$ or the $i$ -th bit in $b$ is equal to $1$ , then the $i$ -th bit in the bitwise OR is equal to $1$ as well. For example, $5_{10} ∣ 9_{10}$ = $010 1_{2} ∣100 1_{2}$ = $110 1_{2}$ = $1 3_{10}$ .

An array $c$ is a subsequence of array $a$ if we can obtain $c$ by deleting some (possibly zero) elements from array $a$ .

Input

The first line contains two integers $n$ ( $1 \leq n \leq 1 0^{6}$ ) and $k$ ( $1 \leq k \leq 30$ ).

The second line contains $n$ integers $a_{i}$ ( $0 \leq a_{i} < 2^{30}$ ).

Output

Print a single integer — the answer to the problem.

Examples

Input #1

Answer #1

Input #2

Answer #2

Input #3

Answer #3

Note

Explanation of the first example:

We can choose $b$ = ${3}$ or $b$ = ${5}$ , since $3$ = $1 1_{2}$ and $5$ = $10 1_{2}$ , and popcount $(3)$ = popcount $(5)$ = $2$ , which is equal to $k$ = $2$ .

Explanation of the second example:

We can choose $b$ = ${7, 8}$ , popcount $(7∣8)$ = popcount $(011 1_{2} ∣100 0_{2})$ = popcount $(111 1_{2})$ = $4$ , which is equal to $k$ = $4$ .

Explanation of the third example:

It can be shown that there is no such subsequence $b$ of array $a$ that satisfies the conditions.

Scoring

It is guaranteed that solutions that work correctly for $n \leq 20$ will receive at least $5$ points.

It is guaranteed that solutions that work correctly for $a_{i} < 1024$ will receive at least $15$ points.

It is guaranteed that solutions that work correctly for $n \leq 1 0^{5}$ will receive at least $85$ points.