Smoke over the water
Along the banks of the Mississippi, there are n wigwams. On a cool summer night, a fire was lit in each one, and throughout the night, the fires burned with consistent intensity.
The scout shaman, Prudent Manul, ventured far from the river that night. During his journey, he climbed an aloe m times to observe the wigwams of his tribe. Each time, he noted a contiguous segment of wigwams and remembered which one had the strongest smoke column.
Using the observations Prudent Manul recalled, determine which wigwams had stronger fires and which had weaker ones. If multiple configurations match Prudent Manul's observations, provide any one of them. If the observations are contradictory, notify Manul.
Input
The first line of the input contains the integers n and m - the number of wigwams and the number of aloe observations, respectively (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000).
Each of the following m lines contains three integers l_i, r_i, and p_i (1 ≤ l_i ≤ p_i ≤ r_i ≤ n), indicating that among the wigwams from l_i to r_i inclusive, the strongest smoke column was from the wigwam numbered p_i.
Output
If the information remembered by Manul is contradictory, output -1. Otherwise, output n distinct numbers from 1 to n, where the i-th number corresponds to the smoke column from the i-th wigwam, with larger numbers indicating stronger smoke columns.