有 $$$n$$$ 斐波那契立方体,其中第 $$$i$$$ 个立方体的边等于 $$$f_{i}$$$,其中 $$$f_{i}$$$ 是第 $$$i$$$ 个斐波那契数。
在这个问题中,斐波那契数的定义如下:
- $$$f_{1} = 1$$$
- $$$f_{2} = 2$$$
- $$$f_{i} = f_{i - 1} + f_{i - 2}$$$ for $$$i \gt 2$$$
还有$$$m$$$个空盒子,其中第$$$i$$$个盒子的宽度为$$$w_{i}$$$,长度为$$$l_{i}$$$,高度为$$$h_{i}$$$。
对于每个 $$$m$$$ 盒子,您需要确定是否所有立方体都可以放入该盒子内。立方体必须按照以下规则放置在盒子中:
- 立方体只能堆叠在盒子中,使得立方体的侧面与盒子的侧面平行;
- 每个立方体必须放置在盒子的底部或其他立方体的顶部,以占据立方体下方的所有空间;
- 较大的立方体无法放置在较小的立方体之上。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — 测试用例的数量。测试用例的描述如下。
在每个测试用例的第一行,有两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10, 1 \le m \le 2 \cdot 10^{5}$$$) — 立方体的数量和空盒子的数量。
每个测试用例接下来的 $$$m$$$ 行包含 $$$3$$$ 整数 $$$w_{i}$$$、$$$l_{i}$$$ 和 $$$h_{i}$$$ ($$$1 \le w_{i}, l_{i}, h_{i} \le 150$$$) - 的维度第 $$$i$$$ 个盒子。
输入的附加限制:
- 所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。
输出
对于每个测试用例,输出长度为 $$$m$$$ 的字符串,其中第 $$$i$$$ 个字符等于 "1" 如果所有 $$$n$$$ 立方体都可以放入第 $$$i$$$ 个盒子中;否则,第 $$$i$$$ 个字符等于 "0".
示例
输入复制
25 43 1 210 10 109 8 1314 7 202 63 3 31 2 12 1 23 2 22 3 13 2 4
输出复制
0010 100101
注意
在第一个测试用例中,只有一个盒子适合。立方体可以如下放置在其中: