B. Fibonacci Cubestime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThere are $$$n$$$ Fibonacci cubes, where the side of the $$$i$$$-th cube is equal to $$$f_{i}$$$, where $$$f_{i}$$$ is the $$$i$$$-th Fibonacci number.In this problem, the Fibonacci numbers are defined as follows: $$$f_{1} = 1$$$ $$$f_{2} = 2$$$ $$$f_{i} = f_{i - 1} + f_{i - 2}$$$ for $$$i > 2$$$ There are also $$$m$$$ empty boxes, where the $$$i$$$-th box has a width of $$$w_{i}$$$, a length of $$$l_{i}$$$, and a height of $$$h_{i}$$$.For each of the $$$m$$$ boxes, you need to determine whether all the cubes can fit inside that box. The cubes must be placed in the box following these rules: The cubes can only be stacked in the box such that the sides of the cubes are parallel to the sides of the box; Every cube must be placed either on the bottom of the box or on top of other cubes in such a way that all space below the cube is occupied; A larger cube cannot be placed on top of a smaller cube. InputEach test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases. The description of the test cases follows.In the first line of each test case, there are two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10, 1 \le m \le 2 \cdot 10^{5}$$$) — the number of cubes and the number of empty boxes.The next $$$m$$$ lines of each test case contain $$$3$$$ integers $$$w_{i}$$$, $$$l_{i}$$$, and $$$h_{i}$$$ ($$$1 \le w_{i}, l_{i}, h_{i} \le 150$$$) — the dimensions of the $$$i$$$-th box.Additional constraints on the input: The sum of $$$m$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$. OutputFor each test case, output a string of length $$$m$$$, where the $$$i$$$-th character is equal to "1" if all $$$n$$$ cubes can fit into the $$$i$$$-th box; otherwise, the $$$i$$$-th character is equal to "0".ExampleInput25 43 1 210 10 109 8 1314 7 202 63 3 31 2 12 1 23 2 22 3 13 2 4Output0010
100101
NoteIn the first test case, only one box is suitable. The cubes can be placed in it as follows: