APIO '12 P2 - Guard

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

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 A_i to the bush B_i. 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.

Task

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

Constraints

1 \le N \le 100\,000 The number of bushes
1 \le K \le N The number of hidden ninjas
1 \le M \le 100\,000 The number of guards

Input Specification

Read the following data from the standard input.

  • The first line of input 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 A_i, B_i, C_i (A_i \le B_i), describing that the guard i is watching from the bush A_i to the bush B_i. The integer C_i is either 0 or 1. If C_i = 0, there is no ninja from the bush A_i to the bush B_i. If C_i = 1, there is at least one ninja from the bush A_i to the bush B_i.

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 Specification

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.

Grading

In test cases worth 10\% of the full score, N \le 20, M \le 100.
In test cases worth 50\% of the full score, N \le 1\,000, M \le 1\,000.

Sample Input 1

5 3 4
1 2 1
3 4 1
4 4 0
4 5 1

Sample Output 1

3
5

In this example, 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.

Sample Input 2

5 1 1
1 5 1

Sample Output 2

-1

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


Comments


  • 1
    maxcruickshanks  commented on Feb. 27, 2022, 7:51 p.m.

    Since the original data were weak, an additional, large test case was added to each batch for full scores.