负责人

• 035966_L3

题目描述

struct S
{
	bool c[5012];
    int dc[5012][2];
	int ts = 1;
    int x;
	void init(int h)
	{
		memset(c, 0, sizeof c);
        memset(dc, 0, sizeof dc);
		c[1] = 0;
		ts = 1;
        x = h;
	}
	void add(int num)
	{
		int now = 1;
		for (int i = 1, j = x; j >= 0; i++, j--)
		{
			bool cc = num & (1 << j);
			int xx = ts + 1;
			if (dc[now][cc]) xx = dc[now][cc];
			if (xx > ts)
			{
				ts++;
				dc[now][cc] = ts;
				c[ts] = cc;
			}
			now = xx;
		}
	}
};

以上是一份 01 Trie 代码。

该代码实现的 01 Trie 可以将任何 $[0,2^x)$ 范围内的整数通过 add 函数进行存储。存储完毕后，变量 ts 的值反映了这棵 01 Trie 所使用的实际空间。

现在，你被允许向一棵由上述代码实现的 01 Trie 中加入 $y$ 个 $[0,2^x)$ 范围内的整数。请加入合适的整数，使得这棵 01 Trie 所使用的实际空间最大。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示该测试点的数据组数。

下面 $T$ 行，每行两个正整数 $x,y$。

输出格式

对于每组数据，输出一行 $y$ 个 $[0,2^x)$ 范围内的整数，表示你加入的整数。

样例

6
1 1
1 2
2 1
2 2
2 3
2 4

1
0 1
0
1 2
3 0 1
2 3 0 1

提示

样例解释：

$6$ 组数据中变量 ts 的值分别为 $2,3,3,5,6,7$。

请注意，答案不是唯一的。

$1 \le T \le 2046$，$1 \le x \le 10$，$1 \le y \le 2^x$。