/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
2 以上の整数 N と、 2 以上 \frac{N(N+1)}{2} 以下の整数 M が与えられます。非負整数からなる集合 A であって、以下の条件をすべて満たすものが存在するので、それを 1 つ構築してください。
- 0 \in A
- 2^N - 1 \in A
- 集合 A の要素はすべて 0 以上 2^N - 1 以下の非負整数である（16:08 修正）
- x, y \in A ならば x ~ \mathrm{AND} ~ y \in A
- x, y \in A ならば x ~ \mathrm{OR} ~ y \in A
- A の要素数 |A| は M に等しい
T 個のテストケースが与えられるので、それぞれについて答えてください。
\mathrm{AND} とは
非負整数 n, m の bit ごとの論理積 n ~ \mathrm{AND} ~ m は、以下のように定義されます。- n ~ \mathrm{AND} ~ m を二進表記した際の 2^k ~ (k \geq 0) の位の数は、 n,m を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1 、そうでなければ 0 である。
\mathrm{OR} とは
非負整数 n, m の bit ごとの論理和 n ~ \mathrm{OR} ~ m は、以下のように定義されます。- n ~ \mathrm{OR} ~ m を二進表記した際の 2^k ~ (k \geq 0) の位の数は、 n,m を二進表記した際の 2^k の位の数のうちいずれか（両方でもよい）が 1 であれば 1 、そうでなければ 0 である。
制約
- 1 \leq T \leq 30
- 2 \leq N \leq 60
- 2 \leq M \leq \frac{N(N+1)}{2}
- 入力はすべて整数
部分点
- 追加の制約 N \leq 5 を満たすデータセットに正解した場合は 25 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
\text{case}_i\ (1 \leq i \leq T) は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。
N M
出力
T 行出力せよ。
i 行目 (1 \leq i \leq T) には、i 番目のテストケースにおいて、問題文の条件をすべて満たす非負整数からなる集合 A の、相異なる M 個の要素を x_1, x_2, \dots, x_M として、以下の形式で出力せよ。
x_1 x_2 \cdots x_M
x_1, x_2, \dots, x_M は昇順でなくても構わない。
なお、この制約下で答えが必ず存在することが証明できる。
入力例 1
3 3 5 4 8 60 2
出力例 1
0 1 3 5 7 0 1 3 7 8 9 11 15 0 1152921504606846975
1 番目のテストケースにおいて、 A = \{0, 1, 3, 5, 7\} とすると、問題文の条件をすべて満たします。例えば、3 ~ \mathrm{AND} ~ 5 = 1 \in A 、 3 ~ \mathrm{OR} ~ 5 = 7 \in A となります。
条件を満たす A なら何でもよく、以下の出力も認められます。出力する要素が昇順でなくても構いません。
7 1 4 0 5
以下の出力は認められません。 0 \not \in A であるためです。
1 2 3 5 7
以下の出力は認められません。 3, 5 \in A である一方、 3 ~ \mathrm{AND} ~ 5 = 1 \not \in A であるためです。
0 3 4 5 7
また、以下の出力も認められません。集合は多重集合ではないことに注意してください。
7 7 7 0 0
3 番目のテストケースにおいて、出力が 32bit 整数型に収まらない場合があることに注意してください。また、入出力例は部分点の制約を満たさないことに注意してください。