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>
  using namespace std;
  int A[(1 << 19) + 5];
  int cnt[257][(1 << 14) + 5];
  int len[257];
  int sortA[(1 << 19) + 5];
  void sort1(vector<int> &A, int N) {
    assert(N <= (1 << 14));
    for (int k = 0; k < 3; k++) {
      for (int j = 0; j < 256; j++) {
        len[j] = 0;
      }
      int mask = ((1 << (8 * (k + 1))) - 1);
      int shiftVal = 8 * k;
      for (int i = 0; i < N; i++) {
        int indx = (A[i] & mask) >> shiftVal;
        cnt[indx][len[indx]++] = A[i];
      }
      int cntIndx = 0;
      for (int j = 0; j < 256; j++) {
        for (int x = 0; x < len[j]; x++) {
          A[cntIndx++] = cnt[j][x];
        }
      }
      assert(cntIndx == N);
    }
  }
  int n, k;
  int f[(1 << 19) + 5];
  int f2[(1 << 19) + 5];
  vector<int> group[(1 << 19) + 5];
  int submaskAns[(1 << 19) + 5];
  int submaskAns2[(1 << 19) + 5][20];
  int main() {
    scanf("%d%d", &n, &k);
    vector<int> A2(n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &A[i]);
    }
    if (n <= (1 << 8)) {
      for (int j = 0; j < (1 << (k - 1)); j++) {
        for (int i = 0; i < n; i++) {
          A2[i] = A[i] ^ j;
        }
        sort1(A2, n);
        int ans = (1 << k);
        for (int i = 1; i < n; i++) {
          ans = min(ans, A2[i] - A2[i - 1]);
        }
        f[j] = ans;
        f[j ^ ((1 << k) - 1)] = ans;
      }
      for (int j = 0; j < (1 << k); j++) {
        printf("%d ", f[j]);
      }
      printf("\n");
      return 0;
    }
    const int m =
        min(max((int)ceil(log2((((1 << k) - 1) / (n - 1)) + 1.5)), 0), k);
    const int maskM = (1 << m) - 1;
    for (int i = 0; i < n; i++) {
      group[A[i] >> m].push_back(A[i]);
    }
    for (int i = 0; i < (1 << m); i++) {
      submaskAns[i] = (1 << m);
    }
    vector<int> group1(n);
    for (int groupNum = 0; groupNum < (1 << (k - m)); groupNum++) {
      for (int j = 0; j < (1 << m); j++) {
        int N = (int)group[groupNum].size();
        for (int i = 0; i < N; i++) {
          group1[i] = group[groupNum][i] ^ j;
        }
        sort1(group1, N);
        int ans = (1 << k);
        for (int i = 1; i < N; i++) {
          ans = min(ans, group1[i] - group1[i - 1]);
        }
        submaskAns[j] = min(ans, submaskAns[j]);
      }
    }
    for (int i = 0; i < (1 << k); i++) {
      f[i] = submaskAns[i & maskM];
    }
    for (int i = 0; i < (1 << k); i++) {
      for (int j = 0; j <= k; j++) {
        submaskAns2[i][j] = (1 << m);
      }
    }
    for (int x = 1; x <= k - m; x++) {
      int maskX = (1 << x) - 1;
      for (int y = 0; y < (1 << (k - m)); y++) {
        int z = y ^ maskX;
        int xorval = y ^ (maskX >> 1);
        assert((y ^ xorval) - (z ^ xorval) == -1);
        int N = (int)group[y].size();
        int M = (int)group[z].size();
        int mask2 = (1 << (x + m)) - 1;
        for (int j = 0; j < (1 << m); j++) {
          int to_xor = (xorval << m) | j;
          int val1 = 0;
          for (int i = 0; i < N; i++) {
            val1 = max(val1, group[y][i] ^ to_xor);
          }
          int val2 = (1 << k);
          for (int i = 0; i < M; i++) {
            val2 = min(val2, group[z][i] ^ to_xor);
          }
          int ans = val2 - val1;
          submaskAns2[to_xor & mask2][x + m] =
              min(submaskAns2[to_xor & mask2][x + m], ans);
        }
      }
    }
    for (int j = 0; j < (1 << k); j++) {
      for (int i = 0; i <= k; i++) {
        f[j] = min(f[j], submaskAns2[j & ((1 << i) - 1)][i]);
      }
      assert(f[j] < (1 << m) && f[j] > 0);
      if (j >= (1 << (k - 1))) {
        assert(f[j] == f[(1 << k) - j - 1]);
      }
      printf("%d ", f[j]);
    }
    return 0;
  }
  