F - XOR Matching

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

以下の条件を満たす、長さ 2^{M + 1} の数列 a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} を、存在するならば 1 つ構築してください。

  • a0 以上 2^M 未満の整数を、それぞれちょうど 2 つずつ含む。
  • a_i = a_j を満たす任意の i,\ j \ (i < j) について、a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K である。

xor (排他的論理和) とは

整数 c_1, c_2, ..., c_n の xor は以下のように定義されます。

  • c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n を二進表記した際の 2^k (k \geq 0) の位の数は、c_1, c_2, ..., c_n のうち二進表記した際の 2^k の位の数が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。

例えば、3 \ xor \ 5 = 6 です (二進表記すると: 011 xor 101 = 110 です)。

制約

  • 入力は全て整数である。
  • 0 \leq M \leq 17
  • 0 \leq K \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

M K

出力

条件を満たす数列 a が存在しなければ -1 を出力せよ。

存在するならば、a の要素を空白区切りで出力せよ。

条件を満たす数列が複数存在する場合、どれを出力してもよい。


入力例 1

1 0

出力例 1

0 0 1 1

このケースでは、条件を満たす数列は複数存在します。

例えば a = {0, 0, 1, 1} の場合、a_i = a_j を満たす (i,\ j)\ (i < j) として (1, 2)(3, 4) があります。a_1 \ xor \ a_2 = 0,\ a_3 \ xor \ a_4 = 0 であるため、この a は与えられた条件を満たしています。


入力例 2

1 1

出力例 2

-1

条件を満たす数列は存在しません。


入力例 3

5 58

出力例 3

-1

条件を満たす数列は存在しません。

Score : 600 points

Problem Statement

Construct a sequence a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} of length 2^{M + 1} that satisfies the following conditions, if such a sequence exists.

  • Each integer between 0 and 2^M - 1 (inclusive) occurs twice in a.
  • For any i and j (i < j) such that a_i = a_j, the formula a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K holds.

What is xor (bitwise exclusive or)?

The xor of integers c_1, c_2, ..., c_n is defined as follows:

  • When c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.

For example, 3 \ xor \ 5 = 6. (If we write it in base two: 011 xor 101 = 110.)

Constraints

  • All values in input are integers.
  • 0 \leq M \leq 17
  • 0 \leq K \leq 10^9

Input

Input is given from Standard Input in the following format:

M K

Output

If there is no sequence a that satisfies the condition, print -1.

If there exists such a sequence a, print the elements of one such sequence a with spaces in between.

If there are multiple sequences that satisfies the condition, any of them will be accepted.


Sample Input 1

1 0

Sample Output 1

0 0 1 1

For this case, there are multiple sequences that satisfy the condition.

For example, when a = {0, 0, 1, 1}, there are two pairs (i,\ j)\ (i < j) such that a_i = a_j: (1, 2) and (3, 4). Since a_1 \ xor \ a_2 = 0 and a_3 \ xor \ a_4 = 0, this sequence a satisfies the condition.


Sample Input 2

1 1

Sample Output 2

-1

No sequence satisfies the condition.


Sample Input 3

5 58

Sample Output 3

-1

No sequence satisfies the condition.