Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

divide and conquer

trees

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. XOR and Distance

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given an array $$$a$$$ consisting of $$$n$$$ distinct elements and an integer $$$k$$$. Each element in the array is a non-negative integer not exceeding $$$2^k-1$$$.

Let's define the XOR distance for a number $$$x$$$ as the value of

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

For every integer $$$x$$$ from $$$0$$$ to $$$2^k-1$$$, you have to calculate $$$f(x)$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$). All these integers are distinct.

Output

Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.

Examples

Input

3 3 6 0 3

Output

3 1 1 2 2 1 1 3

Input

3 4 13 4 2

Output

2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2

Note

Consider the first example:

- for $$$x = 0$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[6, 0, 3]$$$, and the minimum absolute difference of two elements is $$$3$$$;
- for $$$x = 1$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[7, 1, 2]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 2$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[4, 2, 1]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 3$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[5, 3, 0]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 4$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[2, 4, 7]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 5$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[3, 5, 6]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 6$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[0, 6, 5]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 7$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[1, 7, 4]$$$, and the minimum absolute difference of two elements is $$$3$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2024 09:35:29 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|