시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Kraw the Krow has N cows. Each cow wears a tag containing a unique number from 0 to N − 1. The cows are lined up in a row in some unknown order. The positions of the cows are labelled from 0 to N − 1 in order.

For reasons that we will probably never know, Kraw found the need to answer an embarrassingly large number of Range Minimum Queries (RMQs). RMQs are questions of the form, ”What is the smallest tag number of the cows standing at or between positions L and R?”

Kraw is very lazy, so he paid Coco the Code Monkey less than minimum wage to solve the RMQs for him. Coco completed all of them four minutes before the deadline, and Kraw was very pleased.

That was in 2013. Now, Kraw is making a big loss in his Cow Tagging conglomerate and is starting to doubt the authenticity of Coco’s work. For all he knew, Coco could have just randomly generated answers to all the RMQs.

Unfortunately, after so many years, all the cows have dispersed and Coco is suspisciously uncontactable. Help Kraw check if there exists any ordering of cows such that all of Coco’s answers are valid.

입력

Your program should read the input from standard input. The input consists of:

  • one line with two integers N (1 ≤ N ≤ 100 000), the number of cows, and Q (1 ≤ Q ≤ 100 000), the number of RMQs;
  • Q lines, with the i-th line containing three integers: Li and Ri (0 ≤ Li ≤ Ri < N), the left and right bounds of the i-th RMQ, and Ai (0 ≤ Ai < N), Coco’s answer to the RMQ.

출력

Output one line containing N space-separated integers: any possible ordering of cows such that Ai is the correct answer to the RMQ [Li, Ri] for all i, and no two cows share the same tag number.

If there does not exist any such ordering of cows, fill all N integers with −1.

예제 입력 1

5 3
0 2 1
1 3 0
1 4 0

예제 출력 1

1 4 3 0 2

First, we note that our proposed ordering [1, 4, 3, 0, 2] is indeed a permutation (that is, every integer from 0 to 4 appears exactly once). Then, we check the RMQs:

  • The first RMQ (L = 0, R = 2) refers to the subarray [1, 4, 3]. The smallest tag number within that range is 1.
  • The second RMQ refers to the subarray [4, 3, 0]. The smallest tag number within that range is 0.
  • The third RMQ refers to the subarray [4, 3, 0, 2]. The smallest tag number within that range is 0.

Since all answers coincide with Coco’s answers, [1, 4, 3, 0, 2] is indeed a valid solution.

예제 입력 2

3 2
0 1 1
1 2 1

예제 출력 2

-1 -1 -1

If the 0-th cow were in position 0 or 1, the answer to the first RMQ would be 0 instead of 1. If the 0-th cow were in position 2, the answer to the second RMQ would be 0 instead of 1. Thus, it is impossible to order the cows such that all RMQs are satisfied.