403541: GYM101192 C A lost array

Fortune smiled upon little Lyosha: he managed to get a very rare and unique array A, which consists of n integers. Having obtained such a precious object, the boy immediately brought it to his underground laboratory so as to fathom the mystery of the array's structure. As an experienced researcher, Lyosha decided not to hurry with performing all the horrible experiments with the poor array, but to observe it at first. On a piece of paper he made some notes on m observations of the array. Each observation is described by 3 numbers l_i, r_i and s_i, which mean, that the sum of elements modulo 2 on the subsegment [l_i, r_i] of the array equals s_i. Lyosha has prepared everything required for the (m + 1)-th observation, but at that point he heard his mother calling him for dinner. Once the boy returned to his lab after the dinner, he shuddered with horror: the array was gone. At all. All the hopes of the little boy of getting the Nobel Prize in the field of array research have vanished in no time. However Lyosha remembered, that he still had some information left about the array. Based on the facts he had previously written down, he decided to build a virtual prototype of the array and conduct experiments with it. Of course, the little boy realized there was no way he could restore an identical copy of the lost array, because there are infinitely many arrays which comply with his previously written down observations. Certainly, all of us know, that operations with huge numbers take huge amount of time, and things get even worse when it comes to negative ones. In order to make his computer prototype as fast as possible, little Lyosha decided to build an array that complies with his notes, its elements are all non-negative and their sum is as small as possible. Help him to do it!

The first line of the input contains two integers n and m — the size of the lost array and the number of observations, which little boy made about it. Then m lines follow. The i-th line contains three integers l_i, r_i and s_i - description of the i-th observation.

Print n integers a_i - elements of the brand new array. If there are several possible arrays, print lexicographically minimal of them. Formally, an array X is lexicographically less then array Y if there is such number k ≤ |X|, that for all i < k X_i = Y_i and X_k < Y_k.

3 3
2 2 1
3 3 0
2 3 1

0 1 0