Circular XOR Popcount Sequence

Given a sequence of non-negative integers \(a_1, a_2, \ldots, a_n\) and a positive integer \(k\), construct a sequence of non-negative integers \(b_1, b_2, \ldots, b_n\) such that:

• For every \(1 \le i \le n\), \(0 \le b_i < 2^k\).
• For every \(1 \le i \le n\), \(\operatorname{popcount}(b_i \oplus b_{(i \bmod n) + 1}) = a_i\), where \(\oplus\) denotes bitwise XOR and \(\operatorname{popcount}(x)\) is the number of 1's in the binary representation of \(x\).

The sequence is circular; that is, we consider \(b_{n+1} = b_1\). If there exists a sequence \(b\) satisfying the conditions, output any valid sequence. Otherwise, output \(-1\).

Note: You can earn partial credit if you correctly judge the existence of a solution.

inputFormat

The first line contains two integers \(n\) and \(k\). The second line contains \(n\) space-separated non-negative integers \(a_1, a_2, \ldots, a_n\).

outputFormat

If a valid sequence \(b_1, b_2, \ldots, b_n\) exists, output the sequence in one line with each number separated by a space. Otherwise, output \(-1\).

sample

1 3
0

0