Есть набор из $$$n$$$ кубиков Фибоначчи, сторона $$$i$$$-го кубика в наборе равна $$$f_{i}$$$, где $$$f_{i}$$$ — $$$i$$$-е число Фибоначчи.
В данной задаче числа Фибоначчи задаются следующим образом:
Также существует $$$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$$$, где $$$i$$$-й символ равен «1», если в $$$i$$$-ю коробку можно поместить все $$$n$$$ кубиков, иначе $$$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
В первом наборе входных данных подходит только одна коробка. Разместить в ней кубики можно следующим образом:
