1553_H. XOR and Distance_109
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. 
/**
 * author: derrick20
 * created: 8/3/21 10:08 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class H_XORDistance {
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        int elems = sc.nextInt();
        int n = sc.nextInt();
        int N = 1 << n;
        // explicit version first: subtree level, mask
        int[][] minimum = new int[n + 1][N];
        int[][] maximum = new int[n + 1][N];
        int[][] dp = new int[n + 1][N];
        int oo = (int) 1e6;
        for (int row = 0; row <= n; row++) {
            Arrays.fill(minimum[row], oo);
            Arrays.fill(maximum[row], -oo);
            Arrays.fill(dp[row], oo);
        }
        for (int i = 0; i < elems; i++) {
            int x = sc.nextInt();
            minimum[0][x] = maximum[0][x] = 0;
        }
        for (int k = 1; k <= n; k++) {
            int b = 1 << (k - 1);
            for (int x = 0; x < N; x++) {
                if ((x & b) == 0) {
                    int y = x ^ b;
                    int interPairs = min(dp[k - 1][x], dp[k - 1][y]);
                    dp[k][y] = min(interPairs, (minimum[k - 1][x] ^ b) - maximum[k - 1][y]);
                    dp[k][x] = min(interPairs, (minimum[k - 1][y] ^ b) - maximum[k - 1][x]);
                    minimum[k][x] = min(minimum[k - 1][x], minimum[k - 1][y] ^ b);
                    maximum[k][x] = max(maximum[k - 1][x], maximum[k - 1][y] ^ b);
                    minimum[k][y] = min(minimum[k - 1][y], minimum[k - 1][x] ^ b);
                    maximum[k][y] = max(maximum[k - 1][y], maximum[k - 1][x] ^ b);
                }
            }
//            System.out.println(Arrays.toString(dp[k]));
        }
        for (int x = 0; x < N; x++) {
            out.print(dp[n][x] + " ");
        }
        out.println();
        out.close();
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
    
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
    
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
    
        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
    
        int nextInt() {
            return (int) nextLong();
        }
    
        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
    
        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }
    
        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}