题目描述

有 $n$ 个斐波那契立方体。其中第 $i$ 个立方体的边长等于 $f_{i}$ ，而 $f_{i}$ 是斐波那契数列的第 $i$ 项。在本问题中，斐波那契数列的定义如下：

• $f_1 = 1;$
• $f_2 = 2;$
• $f_{i} = f_{i - 1} + f_{i - 2}$，$i > 2$。

还有 $m$ 个空盒子，其中第 $i$ 个盒子的长为 $l_i$，宽为 $w_i$，高为 $h_i$。盒子不能翻转或放倒。

对于每个盒子，你需要确定是否所有的立方体都能放入盒子里。必须按照以下规则将立方体放入盒子中：

• 立方体只能堆叠在盒子里，使立方体的侧面与盒子的侧面平行；
• 每个立方体都必须放在盒子的底部或其他立方体的顶部，以确保立方体下方的所有空间都被占满；
• 较大的立方体不能放在较小的立方体上面。

可以参考样例解释中的图片进一步理解。

输入格式

输入包含多组测试数据。第一行一个正整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行两个正整数 $n$ 和 $m$ 分别表示方块数和空盒子数。

接下来 $m$ 行，每行包含 $3$ 个正整数 $w_{i}$，$l_{i}$ 和 $h_{i}$ 表示第 $i$ 个盒子的长、宽、高。

输出格式

对于每组测试数据，输出长度为 $m$ 的字符串 $s$，其中，如果所有立方体都能放入第 $i$ 个盒子，则 $s_i = 1$，否则 $s_i = 0$。

2
5 4
3 1 2
10 10 10
9 8 13
14 7 20
2 6
3 3 3
1 2 1
2 1 2
3 2 2
2 3 1
3 2 4

0010
100101

样例解释

数据规模与约定

下发文件

下发文件对应子任务 $1,2,3,4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^3,2 \leq n,1 \leq m,\sum m \leq 2 \times 10^5,1 \leq l_i,w_i,h_i \leq 150$。