## APIO '12 P2 - Guard

View as PDF

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 bushes. The bushes are numbered from to , and ninjas are hiding in exactly bushes. There are guards in the APIO castle. The guard is watching a sequence of bushes from the bush to the bush . 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

 The number of bushes The number of hidden ninjas The number of guards

#### Input Specification

Read the following data from the standard input.

• The first line of input contains three space separated integers , , , where is the number of bushes, is the number of hidden ninjas, and is the number of guards.
• The following lines contain the information of the guards and the reports from them. The -th line of them contains three space separated integers , , (), describing that the guard is watching from the bush to the bush . The integer is either or . If , there is no ninja from the bush to the bush . If , there is at least one ninja from the bush to the bush .

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 bushes where "a ninja is certainly hiding", the output consists of lines. If there is no bush where "a ninja is certainly hiding", output -1 to the standard output.

In test cases worth of the full score, , .
In test cases worth of the full score, , .

#### 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 , , , or three ninjas are hiding in the bush , , .

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

#### 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.