Restore Array

Your task is to determine one possible binary array A of length N that abides by M given constraints of the form:

• (l, r, k, value) - the k-th smallest element in subarray A[l..r] is value (0 ≤ l ≤ r < N, 1 ≤ k ≤ r - l + 1, 0 ≤ value ≤ 1). Please note that array A is 0-indexed.

The first line of input contains two integers N and M (1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000) - the length of array A and the number of constraints.

The next M lines describe the constraints. Each line contains four integers li, ri, ki, valuei, describing the i-th constraint.

The first line of the output contains N integers - one possible binary array A. If there are several that abide by all M constraints you may output any of them. If there is no such array you must instead output the single integer -1.

There are several binary arrays that abide by all the constraints. One of them is 0 1 0 0 because:

1. The 2-nd smallest element among 0 1 0 0 is 1.
2. The 2-nd smallest element among 0 1 0 0 is 0.
3. The 1-st smallest element among 0 1 0 0 is 0.
4. The 1-st smallest element among 0 1 0 0 is 0.
5. The 1-st smallest element among 0 1 0 0 is 0.