Identifying Hidden Ninjas

APIO Kingdom is under attack by ninjas! These ninjas are very powerful because they can hide in the shadows making them invisible to others. The entire kingdom except the APIO Castle is occupied. In front of the castle there are $N$ bushes numbered from $1$ to $N$. Exactly $K$ ninjas are hiding behind exactly $K$ bushes. Inside the castle, there are $M$ guards. Guard $i$ monitors a contiguous range of bushes from $A_i$ to $B_i$. Each guard reports whether or not there is at least one ninja in his range. In particular, if the report is 1 then there is at least one ninja in the range, and if the report is 0 then there is no ninja among those bushes. Under the constraint that the positions of ninjas (i.e. the set $S\subseteq \{1,2,\dots,N\}$ with $|S|=K$) must be consistent with every guard's report, your task is to determine all bushes that definitely hide a ninja, i.e. bushes $j$ such that in every ninja arrangement consistent with the guard reports, bush $j$ contains a ninja.

More formally, let $x_i$ be 1 if bush $i$ hides a ninja and 0 otherwise. You are given that [ \sum_{i=1}^{N}x_i=K,] and for each guard with report $r$ monitoring bushes from $A$ to $B$, it holds that [ \text{if } r=1, ; \sum_{i=A}^{B} x_i \ge 1 \quad \text{and} \quad \text{if } r=0, ; \sum_{i=A}^{B} x_i = 0.] A bush $j$ is guaranteed to have a ninja if in every solution (assignment) satisfying these conditions, we have $x_j=1$.

Your program should output all such bush numbers in increasing order (separated by spaces).

inputFormat

The first line contains three integers $N$, $K$, and $M$. Each of the following $M$ lines contains three integers $A_i$, $B_i$, and $r_i$, where $A_i$ and $B_i$ ($1 \le A_i \le B_i \le N$) denote the range that guard $i$ monitors and $r_i$ is either 0 or 1 representing the guard’s report.

outputFormat

Output the bush numbers that are guaranteed to hide a ninja in increasing order, separated by a space. If no bush is guaranteed, output an empty line.

sample

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