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;
  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;
  }
  