시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 26 9 9 47.368%

문제

APIO 왕국이 닌자들의 공격을 받고 있다. 닌자들은 공격할 때 그림자에 숨을 수 있고, 다른 사람들은 그들을 볼 수 없기 때문에 닌자들은 매우 강하다. 왕이 살고 있는 APIO 성을 제외한 왕국은 함락 당하였다. APIO 성의 정면에는 N개의 덤불들이 한 줄로 놓여있다. 이 덤불들은 1부터 N까지의 번호가 매겨져 있고, K명의 닌자들이 정확히 K개의 덤불에 숨어있다. APIO성에는 M병의 경비병이 있다. 경비병 i는 덤불 Ai부터 덤불 Bi까지의 연속된 덤불들을 감시한다. 각 경비병은 자기가 경비하는 덤불들에 닌자가 있는지에 대해 보고한다. 여러분은 각 경비병들의 보고를 듣고, 어떤 덤불에 “닌자가 확실히 숨어있”는지를 왕에게 보고해야 한다. 숨어있는 어떠한 닌자들의 배치에 대해서, 한 덤불에 “닌자가 확실히 숨어있”다는 것은 경비병들의 보고와 모순이 되지 않아야 한다.

경비병들의 정보와 그 들의 보고가 주어질 때, "닌자가 확실히 숨어있"는 모든 덤불을 찾아내는 프로그램을 작성하라.

입력

입력의 첫 줄에는 세 개의 정수 N, K, M이 빈칸을 사이에 두고 주어진다. 단, N은 덤불의 수, K는 숨어있는 닌자의 수, M은 경비병의 수이다.

다음 M개의 줄에는 경비병들의 정보와 그 들의 보고가 주어진다. 이들 중 i번째 줄에는 세 개의 정수 Ai, Bi, Ci가 (Ai ≤ Bi) 하나의 빈칸을 사이에 두고 주어지는데, 이는 경비병 i가 감시하고 있는 덤불 Ai부터 덤불 Bi까지를 나타낸다. 또한 Ci는 0 혹은 1의 값이다. 만약 Ci = 0 이라면, Ai 덤불부터 덤불 Bi사이에는 숨어있는 닌자가 없음을 의미하고, Ci = 1 이면, 덤불 Ai부터 덤불 Bi사이에는 적어도 한 명의 닌자가 숨어있음을 나타낸다.

1 ≤ N ≤ 100,000

1 ≤ K ≤ N

1 ≤ M ≤ 100,000

출력

"닌자가 확실히 숨어있"는 덤불이 존재하면, "닌자가 확실히 숨어있"는 덤불의 번호를 출력한다. 덤불의 번호는 오름차순으로 출력되어야 하며, 한 줄에는 하나의 번호만 출력하여야 한다. 그러므로, 만약 "닌자가 확실히 숨어있"는 덤불이 X개이면, X개의 줄에 출력을 하여야 한다. "닌자가 확실히 숨어있"는 덤불이 하나도 없다면, -1을 출력한다

예제 입력

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

예제 출력

3
5

힌트

이 예에서는 조건을 만족하는 닌자의 배치가 두 가지가 있다: 세 닌자가 덤불 1, 3, 5 에 숨어있거나 세 닌자가 덤불 2, 3, 5 에 숨어있을 수 있다. 닌자의 어떤 배치에서도 덤불 3 과 5 에 닌자가 숨어있으므로, 3 과 5 를 출력하여야 한다. 덤불 1 에 대해서는, 덤불 1 에 닌자가 숨어있는 배치도 존재하지만, 덤불 1 에 닌자가 숨어있지 않는 배치도 존재한다. 그러므로, 1 은 출력하지 않아야 한다. 같은 이유로 2 도 출력하지 않아야 한다.