P3634 [APIO2012] Guard

The APIO Kingdom is under attack by ninjas! Ninjas are very skilled, because during their attack they can hide in the shadows so that others cannot see them. The entire kingdom has been occupied except for the APIO castle where the king resides.

In front of the castle, there are $N$ bushes, numbered from $1$ to $N$. There are $K$ ninjas hiding behind exactly $K$ bushes. There are $M$ guards in the APIO castle. Guard $i$ watches a contiguous segment of bushes numbered from $A_i$ to $B_i$. Each guard reports to the king whether there is a ninja within their monitored range. As the king’s servant, you need to tell the king, based on the guards’ reports, which bushes must contain a ninja; that is, for any placement of ninjas that is consistent with the reports, there is a ninja behind that bush. Output all such bush indices.

The first line contains three space-separated integers $N, K, M$. $N$ is the number of bushes, $K$ is the number of ninjas, and $M$ is the number of guards. The next $M$ lines each describe one guard. The $i$-th line contains three integers $A_i, B_i, C_i$, meaning that the $i$-th guard monitors the range from $A_i$ to $B_i$ (with $A_i \leq B_i$). $C_i$ is $0$ or $1$: $0$ means no ninja is seen within the range; $1$ means there is at least one ninja within the range. The input guarantees that at least one placement of ninjas satisfies all constraints.

If there exist bushes that must contain a ninja, output their indices in increasing order, one per line. If there are $X$ such bushes, output $X$ lines. Otherwise, output a single line containing `-1`.

#### Sample Explanation $1$ In this sample, there are two possible placements: $1, 3, 5$ or $2, 3, 5$. Therefore, $3$ and $5$ must contain a ninja. For bush $1$, there exists a placement where it has a ninja and another where it does not, so $1$ should not be output. Similarly, $2$ should not be output. #### Sample Explanation $2$ In this sample, no bush is guaranteed to contain a ninja. #### Constraints $1 \leq N \leq 10^5$; $1 \leq K \leq N$; $0 \leq M < 10^5$. For $10\%$ of the testdata, $N \leq 20$, $M \leq 100$. For $50\%$ of the testdata, $N \leq 1000$, $M \leq 1000$. Translated by ChatGPT 5