#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
vector<T> make_unique(vector<T> a) {
  sort((a).begin(), (a).end());
  a.erase(unique((a).begin(), (a).end()), a.end());
  return a;
}
const int INF = 1e9;
struct node {
  node *left, *right;
  int len, ans, mn, mx;
  node(int len)
      : len(len), ans(INF), mn(INF), mx(-INF), left(nullptr), right(nullptr) {}
  void pull() {
    if (len == 1) return;
    ans = min(get_ans(left), get_ans(right));
    ans = min(ans, get_mn(right) + len / 2 - get_mx(left));
    mn = min(get_mn(left), len / 2 + get_mn(right));
    mx = max(get_mx(right) + len / 2, get_mx(left));
  }
  void build() {
    if (left) left->build();
    if (right) right->build();
    pull();
  }
  void flip_depth(int depth) {
    if (depth == 0) {
      swap(left, right);
      pull();
    } else {
      if (left) left->flip_depth(depth - 1);
      if (right) right->flip_depth(depth - 1);
      pull();
    }
  }
  void print(string tab = "") {
    cerr << tab << "len: " << len << " ans: " << ans << " mn: " << mn
         << " mx: " << mx << endl;
    if (left) left->print(tab + "  ");
    if (right) right->print(tab + "  ");
  }

 private:
  int get_ans(node *u) { return u ? u->ans : INF; }
  int get_mn(node *u) { return u ? u->mn : INF; }
  int get_mx(node *u) { return u ? u->mx : -INF; }
};
int rev(int mask, int k) {
  int ans = 0;
  for (int i = 0; i < (int)(k); i++) {
    ans = 2 * ans + (mask >> i) % 2;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < (int)(n); i++) cin >> a[i];
  auto root = new node(1 << k);
  for (auto x : a) {
    auto cur = root;
    for (int bit = k - 1; bit >= 0; bit--) {
      auto &go = (((x >> bit) & 1) ? cur->right : cur->left);
      if (go == nullptr) go = new node(cur->len / 2);
      cur = go;
    }
    cur->len = 1;
    cur->mn = cur->mx = 0;
  }
  root->build();
  vector<int> ans(1 << k);
  int last = 0;
  for (int mask = 0; mask < (int)(1 << k); mask++) {
    auto change = mask ^ last;
    for (int i = 0; i < (int)(k); i++)
      if ((change >> i) & 1) root->flip_depth(i);
    ans[rev(mask, k)] = root->ans;
    last = mask;
  }
  for (auto x : ans) cout << x << ' ';
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

You 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_{i = 1}^{n} min_{j = i + 1}^{n} |(a_i ⊕ x) - (a_j ⊕ x)|,$$$

where ⊕ denotes [the bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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 ≤ k ≤ 19; 2 ≤ n ≤ 2^k).

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
vector<T> make_unique(vector<T> a) {
  sort((a).begin(), (a).end());
  a.erase(unique((a).begin(), (a).end()), a.end());
  return a;
}
const int INF = 1e9;
struct node {
  node *left, *right;
  int len, ans, mn, mx;
  node(int len)
      : len(len), ans(INF), mn(INF), mx(-INF), left(nullptr), right(nullptr) {}
  void pull() {
    if (len == 1) return;
    ans = min(get_ans(left), get_ans(right));
    ans = min(ans, get_mn(right) + len / 2 - get_mx(left));
    mn = min(get_mn(left), len / 2 + get_mn(right));
    mx = max(get_mx(right) + len / 2, get_mx(left));
  }
  void build() {
    if (left) left->build();
    if (right) right->build();
    pull();
  }
  void flip_depth(int depth) {
    if (depth == 0) {
      swap(left, right);
      pull();
    } else {
      if (left) left->flip_depth(depth - 1);
      if (right) right->flip_depth(depth - 1);
      pull();
    }
  }
  void print(string tab = "") {
    cerr << tab << "len: " << len << " ans: " << ans << " mn: " << mn
         << " mx: " << mx << endl;
    if (left) left->print(tab + "  ");
    if (right) right->print(tab + "  ");
  }

 private:
  int get_ans(node *u) { return u ? u->ans : INF; }
  int get_mn(node *u) { return u ? u->mn : INF; }
  int get_mx(node *u) { return u ? u->mx : -INF; }
};
int rev(int mask, int k) {
  int ans = 0;
  for (int i = 0; i < (int)(k); i++) {
    ans = 2 * ans + (mask >> i) % 2;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < (int)(n); i++) cin >> a[i];
  auto root = new node(1 << k);
  for (auto x : a) {
    auto cur = root;
    for (int bit = k - 1; bit >= 0; bit--) {
      auto &go = (((x >> bit) & 1) ? cur->right : cur->left);
      if (go == nullptr) go = new node(cur->len / 2);
      cur = go;
    }
    cur->len = 1;
    cur->mn = cur->mx = 0;
  }
  root->build();
  vector<int> ans(1 << k);
  int last = 0;
  for (int mask = 0; mask < (int)(1 << k); mask++) {
    auto change = mask ^ last;
    for (int i = 0; i < (int)(k); i++)
      if ((change >> i) & 1) root->flip_depth(i);
    ans[rev(mask, k)] = root->ans;
    last = mask;
  }
  for (auto x : ans) cout << x << ' ';
  return 0;
}

```