Smoke over the water#4337
Along the banks of the Mississippi, there are wigwams. On one cool summer night, a fire burned in each of them, and throughout the night, the strength of each fire remained constant.
The reconnaissance shaman, Sensible Manul, spent the night wandering far from the river. During this night, he climbed an aloe times to observe the wigwams of his native tribe. Each time, he saw a sequence of wigwams forming a contiguous segment and remembered which of them had the strongest column of smoke.
Based on the observations Sensible Manul remembered, reconstruct which wigwams had stronger fires and which had weaker ones. If there are several arrangements that fit Manul's description, output any of them. If the data is contradictory, inform Manul about it.
The first line of the input file contains the integers and — the number of wigwams and the number of aloe climbs, respectively (1 \leq n \leq 100000, 0 \leq m \leq 100000).
Each of the next lines contains three integers l_i, r_i, and p_i (1 \leq l_i \leq p_i \leq r_i \leq n), meaning that among the wigwams from the l_i-th to the r_i-th inclusively, the strongest column of smoke came from the wigwam numbered p_i.
If Manul's remembered information is contradictory, output -1. Otherwise, output distinct integers from to , where the -th number corresponds to the column of smoke from the -th wigwam — larger numbers correspond to stronger columns of smoke.
Example 1