题目描述

有 $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$ 个盒子的宽度为 $w_i$，长度为 $l_i$，高度为 $h_i$。

对于这 $m$ 个盒子中的每一个，你需要判断是否所有的立方体都能放入该盒子中。立方体必须按照以下规则放置：

• 立方体只能堆叠在盒子中，且立方体的边必须与盒子的边平行；
• 每个立方体必须放在盒子的底部或其他立方体的顶部，且下方的空间必须被完全占据；
• 较大的立方体不能放在较小的立方体上。

输入格式

每个测试用例包含多个测试用例。第一行包含一个整数 $t$（$1 ≤ t ≤ 10^3$）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 ≤ n ≤ 10$，$1 ≤ m ≤ 2 × 10^5$）——立方体的数量和盒子的数量。

接下来 $m$ 行，每行包含 $3$ 个整数 $w_i$、$l_i$ 和 $h_i$（$1 ≤ w_i,\ l_i,\ h_i ≤ 150$）——第 $i$ 个盒子的尺寸。

输入的其他约束：

所有测试用例的 $m$ 之和不超过 $2 × 10^5$。

输出格式

对于每个测试用例，输出一个长度为 $m$ 的字符串，其中第 $i$ 个字符为 1 表示所有 $n$ 个立方体可以放入第 $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解释

在第一个测试用例中，只有一个盒子是合适的。立方体可以按照以下方式放入其中：