Exam#210

Exam

1 second
256 megabytes
Medium

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 consisting of integers and an integer . We say that an array with elements is good if popcount(b_1 | b_2 | \dots b_{t-1} | b_t) \ge k, where denotes bitwise OR and popcount() returns the number of ones in the binary representation of . The imbalance of an array is defined as max(b) - min(b), where max and min denote the maximum and the minimum elements of array , respectively.

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

The bitwise OR between two numbers and is defined for each bit separately. If the -th bit in is equal to or the -th bit in is equal to , then the -th bit in the bitwise OR is equal to as well. For example, 5_{10}|9_{10} = 0101_2 | 1001_2 = 1101_2 = 13_{10}.

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

Input

The first line contains two integers (1 \le n \le 10^6) and (1 \le k \le 30).

The second line contains integers a_i (0 \le a_i < 2^{30}).

Output

Print a single integer — the answer to the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

Explanation of the first example:

We can choose = or = , since = 11_2 and = 101_2, and popcount = popcount = , which is equal to = .

Explanation of the second example:

We can choose = , popcount = popcount(0111_2 | 1000_2) = popcount(1111_2) = , which is equal to = .

Explanation of the third example:

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

Scoring

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

It is guaranteed that solutions that work correctly for a_i < 1024 will receive at least points.

It is guaranteed that solutions that work correctly for n \le 10^5 will receive at least points.