#P18491. Set Construction

Set Construction

Set Construction

给定整数 N≥2N\ge2 以及整数 MM,其中 2≤M≤N(N+1)/22\le M\le N(N+1)/2。请构造一个非负整数集合 AA,同时满足以下所有条件:

  • 若 x∈Ax\in A,则 0≤x≤2N−10\le x\le2^N-1。
  • 0∈A0\in A。
  • 2N−1∈A2^N-1\in A。
  • 若 x,y∈Ax,y\in A,则 (xAND⁡y)∈A(x\operatorname{AND}y)\in A。
  • 若 x,y∈Ax,y\in A,则 (xOR⁡y)∈A(x\operatorname{OR}y)\in A。
  • AA 恰有 MM 个元素。

这里 AND 表示按位与运算,OR 表示按位或运算。集合中的元素必须互不相同。

给定 TT 组测试用例,分别求解。可以证明,在本题约束下始终存在合法答案。

输入格式

第一行一个整数 TT。接下来每组测试用例占一行,包含两个整数 N,MN,M。

所有输入值均为整数,满足:

  • 1≤T≤301\le T\le30;
  • 2≤N≤602\le N\le60;
  • 2≤M≤N(N+1)/22\le M\le N(N+1)/2。

输出格式

对于每个测试用例,输出构成集合 AA 的 MM 个互不相同的非负整数,满足上述全部要求。元素顺序任意。不同用例的答案各占一行。

样例

输入:

3
3 5
4 8
60 2

输出:

0 1 3 5 7
0 1 3 7 8 9 11 15
0 1152921504606846975

第一组中,A={0,1,3,5,7}A=\{0,1,3,5,7\} 满足所有条件。例如,(3AND⁡5)=1∈A(3\operatorname{AND}5)=1\in A,(3OR⁡5)=7∈A(3\operatorname{OR}5)=7\in A。

任何合法集合都可以接受,例如 7 1 4 0 5 也是第一组的合法答案;元素不需要按升序输出。

  • 1 2 3 5 7 不合法,因为不包含 00。
  • 0 3 4 5 7 不合法,因为 3,5∈A3,5\in A,但 (3AND⁡5)=1∉A(3\operatorname{AND}5)=1\notin A。
  • 7 7 7 0 0 不合法,因为要求集合而非可重复元素的多重集合。