After getting bored of playing video games, Mike decided to go hiking. Like any good hiker, he brought a map along with him. However, shortly after setting out for the hike, Mike was caught in a rainstorm. Once he found shelter under a nearby tree, Mike realized his map had gotten drenched as well!

Determined to finish his hike, Mike wants you to reconstruct the map. The map is represented as an array of integers, each indicating the elevation at a particular point. Remembering that certain sections of the map were uphill or downhill, Mike will give you $M$ requirements, each in the form $t_i$ $l_i$ $r_i$:

• If $t_i=1$, the subarray from index $l_i$ to index $r_i$ is strictly increasing.
• If $t_i=2$, the subarray from index $l_i$ to index $r_i$ is strictly decreasing.

Mike also has some additional requirements for the map: First of all, he tells you that the trail is never flat, so no two adjacent elements can be equal. Second of all, each element must be a positive integer not exceeding ${10}^9$. Third of all, the maximum element of the array should be as small as possible.

Help Mike reconstruct his map, or tell him that it is impossible to do so.

Constraints

$2\le N\le {10}^6$

$1\le M\le {10}^6$

$t_i\in \{1,2\}$

$1\le l_i<r_i\le N$

Subtask 1 [50%]

$2\le N\le 5000$

$1\le M\le 5000$

If your submission outputs a valid map but does not minimize the maximum element, you will receive $25\mathrm{\%}$ out of the $50\mathrm{\%}$ of points available for this subtask.

Subtask 2 [50%]

No additional constraints.

If your submission outputs a valid map but does not minimize the maximum element, you will receive $25\mathrm{\%}$ out of the $50\mathrm{\%}$ of points available for this subtask.

Input Specification

The first line contains $2$ integers $N$ and $M$.

The $i$-th of the following $M$ lines each contain $3$ integers $t_i,l_i,r_i$, describing a requirement as specified in the statement.

Output Specification

If no valid output exists, output $-1$.

Otherwise, output one line containing $N$ positive integers that satisfy all requirements. Each element must be within the range $[1,{10}^9]$, and no two adjacent elements can be equal.

If there are multiple valid answers, you may output any of them.

Sample Input 1

5 2
1 1 3
2 3 5

Sample Output 1

1 2 3 2 1

Sample Input 2

3 3
1 1 2
1 2 3
2 1 3

Sample Output 2

-1