Competitions

# Guard

The Kingdom of APIO is attacked by ninjas. Ninjas are very strong because, when they attack, they are hiding in the shadows and other people cannot see them. The Kingdom was captured except for the APIO castle, where the king lives. In front of the APIO castle, there is a line of N bushes. The bushes are numbered from 1 to N, and K ninjas are hiding in exactly K bushes. There are M guards in the APIO castle. The guard i is watching a sequence of bushes from the bush Ai to the bush Bi. Now, each guard reports to the king whether there is a ninja in the bushes he/she is watching. Since you are a servant of the king, you have to tell him, based on the reports from the guards, in which bush "a ninja is certainly hiding". Here, "a ninja is certainly hiding" in a bush if a ninja is hiding in it for any possible arrangement of ninjas which does not contradict the reports from the guards.

Write a program that, given information of the guards and the reports from them, determines all bushes where "a ninja is certainly hiding".

Constraints

1N100000 - The number of bushes
1KN - The number of hidden ninjas
1M100000 - The number of guards

Input

The ﬁrst line contains three space separated integers N, K, M, where N is the number of bushes, K is the number of hidden ninjas, and M is the number of guards. The following M lines contain the information of the guards and the reports from them. The i-th line of them contains three space separated integers Ai, Bi, Ci (AiBi), describing that the guard i is watching from the bush Ai to the bush Bi. The integer Ci is either 0 or 1. If Ci = 0, there is no ninja from the bush Ai to the bush Bi. If Ci = 1, there is at least one ninja from the bush Ai to the bush Bi.

For each input, it is guaranteed that there is at least one arrangement of ninjas which does not contradict the reports from the guards.

Output

If there is a bush where "a ninja is certainly hiding", output the numbers of the bushes where "a ninja is certainly hiding" to the standard output. The numbers of bushes should be written in ascending order, and one line of output should contain only one number. Therefore, if there are X bushes where "a ninja is certainly hiding", the output consists of X lines. If there is no bush where "a ninja is certainly hiding", output '-1' to the standard output.

Note Sample

In example 1, there are two possible arrangements of ninjas satisfying the conditions; three ninjas are hiding in the bush 1, 3, 5, or three ninjas are hiding in the bush 2, 3, 5.

Since a ninja is hiding in the bush 3 and 5 for any possible arrangements, we should output 3 and 5. Concerning the bush 1, there is a possible arrangement of ninjas where a ninja is hiding in the bush 1. But there is also a possible arrangement of ninjas where no ninja is hiding in the bush 1. Therefore, we should not output 1. By the same reason, we should not output 2.

In example 2, there is no bush where "a ninja is certainly hiding". Therefore, we should output '-1'.

Time limit 1 second
Memory limit 256 MiB
Input example #1
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1

Output example #1
3
5

Source 2012 Asia-Pacific Informatics Olympiad (APIO), Problem B