description: 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. 
solution: #include <bits/stdc++.h>
  #pragma GCC optimize("O3")
  #pragma GCC optimize("unroll-loops")
  using namespace std;
  int n, k;
  int arr[600006];
  int nxt[600006][20];
  vector<vector<pair<int, pair<int, int> > > > mem;
  vector<vector<bool> > vis;
  int lookup[600006][20];
  int X;
  void build(int bit, int L, int R) {
    if (L == R) return;
    int M = nxt[L][bit];
    lookup[L][bit] = X++;
    if (M == L || M > R)
      build(bit - 1, L, R);
    else {
      build(bit - 1, L, M - 1);
      build(bit - 1, M, R);
    }
  }
  pair<int, pair<int, int> > solve(int bit, int ref, int L, int R) {
    if (L == R)
      return make_pair(100000000,
                       make_pair((arr[L] ^ ref) & ((1 << (bit + 1)) - 1),
                                 (arr[R] ^ ref) & ((1 << (bit + 1)) - 1)));
    while (int(mem[lookup[L][bit]].size()) <= ref)
      mem[lookup[L][bit]].push_back(make_pair(0, make_pair(0, 0))),
          vis[lookup[L][bit]].push_back(false);
    if (vis[lookup[L][bit]][ref]) return mem[lookup[L][bit]][ref];
    vis[lookup[L][bit]][ref] = true;
    int new_ref = ref;
    if (ref & (1 << bit)) new_ref ^= 1 << bit;
    int M = nxt[L][bit];
    if (M == L || M > R) {
      pair<int, pair<int, int> > tmp = solve(bit - 1, new_ref, L, R);
      if ((arr[L] ^ ref) & (1 << bit)) tmp.second.first += (1 << bit);
      if ((arr[L] ^ ref) & (1 << bit)) tmp.second.second += (1 << bit);
      return mem[lookup[L][bit]][ref] = tmp;
    }
    pair<int, pair<int, int> > left = solve(bit - 1, new_ref, L, M - 1);
    pair<int, pair<int, int> > right = solve(bit - 1, new_ref, M, R);
    if (ref & (1 << bit)) swap(left, right);
    pair<int, pair<int, int> > ans;
    ans.first = min(left.first, right.first);
    ans.first =
        min(ans.first, right.second.first - left.second.second + (1 << bit));
    ans.second.first = left.second.first;
    ans.second.second = right.second.second + (1 << bit);
    return mem[lookup[L][bit]][ref] = ans;
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    for (int bit = 0; bit < k; bit++) {
      int lst = n;
      for (int i = n - 1; i >= 0; i--) {
        if (arr[i] & (1 << bit)) lst = i;
        nxt[i][bit] = lst;
      }
    }
    build(k - 1, 0, n - 1);
    vis.resize(X);
    mem.resize(X);
    for (int ref = 0; ref < (1 << k); ref++)
      cout << solve(k - 1, ref, 0, n - 1).first << " ";
    cout << "\n";
    return 0;
  }
  