#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
const int MAX = 100020;

struct report {
    int s, e;

    report() {}
    report(int s, int e) : s(s), e(e) {}

    bool operator < (const report &t) const {
        if(s == t.s) return e < t.e;
        return s < t.s;
    }
};

int n, m, k, yFull, nFull;
report yes[MAX], no[MAX];

void input(){
    scanf("%d%d%d", &n, &k, &m);

    int i;
    for(i = 0; i<m; i++){
        int ts, te, c;
        scanf("%d%d%d", &ts, &te, &c);

        //닌자가 없다는 보고는 no에, 있다는 보고는 yes에 저장
        if(c == 0) no[nFull++] = report(ts, te);
        else yes[yFull++] = report(ts, te);
    }
}

bool none[MAX];
int cnt, lFind[MAX], rFind[MAX];

void init(){
    //보고들을 좌표 순으로 정렬
    sort(yes, yes+yFull);
    sort(no, no+nFull);

    int i, now;

    //닌자가 있다는 보고들을 정리. yes 배열을 스택으로 사용한다.
    now = 1;
    for(i = 1; i<yFull; i++){
        /*
        (s1, e1) (s2, e2)일 때 s1 <= s2 && e2 <= e1이면
        첫 번쨰 보고를 삭제하고 두 번째 보고만 삽입
        */
        while(yFull && yes[now-1].e >= yes[i].e)
            now--;
        yes[now++] = yes[i];
    }
    yFull = now;

    //닌자가 없다는 보고들을 정리
    cnt = n;
    int j = 1;
    for(i = 0; i<nFull; i++){
        if(j < no[i].s) j = no[i].s;
        for(; j <= no[i].e; j++){
            //닌자가 확실히 없는 덤불은 none 배열에 체크
            none[j] = 1;
            cnt--;
        }
    }
    //루프가 끝나면 cnt는 '닌자가 있을 가능성이 있는 덤불의 수'가 된다.

    /*
    lFind[i]는 번호가 i 이하인 덤불 중
    '닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 큰 덤불의 번호
    */
    for(i = 1; i<=n; i++){
        if(!none[i]) lFind[i] = i;
        else lFind[i] = lFind[i-1];
    }

    /*
    rFind[i]는 번호가 i 이상인 덤불 중
    '닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 작은 덤불의 번호
    */
    for(i = n; i>=1; i--){
        if(!none[i]) rFind[i] = i;
        else rFind[i] = rFind[i+1];
    }
}

int left[MAX], lFull, right[MAX], rFull;
vector < int > res;

void solve(){
    int i;
    //'닌자가 숨어있을 가능성이 있는 덤불'이 k개와 일치한다면 k개 전부가 답.
    if(cnt == k){
        for(i = 1; i<=n; i++)
            if(lFind[i] == i)
                res.push_back(i);
    } else {
        int last;

        /*
        k개보다 많다면, 탐욕 알고리즘을 사용해 '보고를 만족하는 최소의 닌자 수'를 구한다.

        닌자들을 놓을 수 있는 가장 오른쪽 칸에 놓아서 채우는 경우, 가장 왼쪽 칸에 놓아서 채우는 경우를 구한다.
        조금 생각해보면 오른쪽에서부터 채울 때와 왼쪽에서 채울 때의 닌자 수가 같다는 것을 알 수 있다. (lFull == rFull)

        닌자들을 최소로 사용하여 채울 때 i번째 닌자가 있을 수 있는 가장 왼쪽 좌표가 left[i], 가장 오른쪽 좌표가 right[i]이다.
        */
        last = 0;
        for(i = 0; i<yFull; i++){
            if(last < yes[i].s){
                left[lFull++] = lFind[yes[i].e];
                last = lFind[yes[i].e];
            }
        }

        last = n+1;
        for(i = yFull-1; i>=0; i--){
            if(last > yes[i].e){
                right[rFull++] = rFind[yes[i].s];
                last = rFind[yes[i].s];
            }
        }

        //닌자를 최소로 사용했을 때 k명인 경우
        if(lFull == k){
            for(i = 0; i<lFull; i++){
                /*
                k명의 닌자 중 존재할 수 있는 가장 왼쪽 좌표와 가장 오른쪽 좌표가 같은 닌자는 위치가 고정되므로 답이 된다.
                그렇지 않은 닌자들은 최소 좌표와 최대 좌표 중 다른 칸에 존재할 수 있는 가능성이 있기 때문에 답이 될 수 없다.
                */
                if(left[i] == right[rFull-1-i]){
                    res.push_back(left[i]);
                }
            }
        //닌자를 최소로 사용했을 때 k명보다 작은 경우 (보고를 만족하는 배치가 존재하기 때문에 k보다 클 수는 없다.)
        } else {
            for(i = 0; i<yFull; i++){
                /*
                닌자를 발견했다는 보고에 대해, 보고 범위 이내에 '닌자가 숨어 있을 가능성이 있는 덤불'이 하나인 경우만 답이 된다.

                그렇지 않은 덤불들은 닌자가 숨어 있을 가능성이 있는 덤불 중
                그 덤불의 바로 왼쪽 덤불과 바로 오른쪽 덤불을 대체해서 선택하면
                그 덤불을 선택하지 않고도 모든 보고를 만족시킬 수 있다.

                이 경우 닌자의 총 인원 수가 증가할수도 있지만, 현재 닌자 수가 k보다 작기 때문에 상관 없다.
                */
                if(lFind[lFind[yes[i].e]-1] < yes[i].s)
                    res.push_back(lFind[yes[i].e]);
            }
        }
    }

    //정답을 출력한다.
    if(res.empty()) puts("-1");
    else {
        for(i = 0; i<res.size(); i++)
            printf("%d\n", res[i]);
    }
}

int main(){
    input();

    init();
    solve();

    return 0;
}

APIO 2012 경비병(Guard) 코드 및 주석입니다.