AT_ttpc2023_j Set Construction

$ 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 $ である。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ は昇順でなくても構わない。 なお、この制約下で答えが必ず存在することが証明できる。

### 部分点 - 追加の制約 $ N \leq 5 $ を満たすデータセットに正解した場合は $ 25 $ 点が与えられる。 ### Sample Explanation 1 $ 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 整数型に収まらない場合があることに注意してください。また、入出力例は部分点の制約を満たさないことに注意してください。 ### Constraints - $ 1 \leq T \leq 30 $ - $ 2 \leq N \leq 60 $ - $ 2 \leq M \leq \frac{N(N+1)}{2} $ - 入力はすべて整数