Однажды вечером Рудольф шел по улице и нашел массив длины $$$n$$$, состоящий из $$$0$$$ и $$$1$$$. Придя домой, Рудольф стал развлекаться с массивом, записывая сумму элементов на различных отрезках массива.
На следующий день, пока Рудольф был на работе, Байер нашел этот массив. Как любой уважающий себя пёсик он его съел. Придя домой, Рудольф понял в чем дело и сильно расстроился. Но позже вспомнил, что у него осталось $$$m$$$ записей про отрезки массива вида $$$l, r, s$$$, где $$$l$$$ и $$$r$$$ — границы отрезка, а $$$s$$$ — сумма элементов на нем. Поскольку Рудольф был уставший прошлым вечером, отрезки, на которых он считал сумму, были длиной не более 10.
Рудольф попросил вас помочь ему восстановить любой подходящий массив. Гарантируется, что ответ существует.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов.
Первая строка набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^4$$$) — размер массива и количество записей, соответственно.
Следующие $$$m$$$ строк содержат по три целых числа $$$l_i, r_i, s_i$$$ ($$$1 \le l_i \le r_i \le n, 0 \le s_i \le r_i - l_i + 1, r_i - l_i \lt 10$$$) — границы $$$i$$$-го отрезка, включительно и сумма элементов на нем.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$. Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^4$$$.
Для каждого набора входных данных выведите в отдельной строке $$$n$$$ чисел ($$$0$$$ или $$$1$$$) через пробел — подходящий массив. Если существует несколько решений, выведите любое.
35 21 4 32 5 33 11 3 221 101 8 45 9 14 13 513 18 416 17 118 20 018 21 14 8 213 15 38 17 7
0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 0 1
Во втором примере также подойдут массивы $$$[1, 0, 1]$$$ и $$$[1, 1, 0]$$$.
