Problem : 242 - Guard

Problem Statistics

Solved Member: 7　　Submission: 40　　User Tried: 8

Statement:

APIO王國正在被忍者攻擊。忍者非常有威脅性，因為攻擊時他/她們會躲在影子中並且不讓任何人發現。除了國王所在的城堡，APIO王國已全數被攻陷。

在城堡正前方，有一排共 N 個灌木叢。灌木叢的編號由1 到 N，而有 K 個忍者恰巧躲在 K 個灌木叢中。

城堡中有 M 個衛兵，衛兵 i 監視著編號 Ai 到 Bi 的連續灌木叢。每位衛兵會回報國王是否有忍者躲在他/她監視的灌木叢中。

現在你必須根據衛兵的回報，告訴國王哪一個(些)灌木叢中「一定有忍者」。

所謂「一定有忍者」，指的是對所有滿足衛兵回報的忍者藏身可能狀況，該灌木叢都躲著忍者。

Task:

寫一個程式，根據衛兵的監視範圍和回報資訊，找出所有「一定有忍者」的灌木叢。

Input:Output:

第一行包含三個用空格隔開的整數N、K 和 M，其中 N 為灌木叢數量，K 為躲藏的忍者數量，M 為衛兵數量。

接下來的M 行包含衛兵監視的範圍和回報結果，第 i 行包含三個用空格隔開的整數Ai、Bi、Ci (Ai ≤ Bi)，描述衛兵 i 監視著 Ai 到 Bi 的灌木叢；Ci 不是 1 就是 0，當Ci = 0代表沒有忍者躲在 Ai 到 Bi 的灌木叢中，當Ci = 1 代表至少有一位忍者躲在 Ai 到 Bi的灌木叢中。

對於每個測資，保證至少有一種忍者躲藏的情況合乎衛兵的回報。

可以保證：
灌木叢數量(N), 1 ≤ N ≤ 100 000
躲藏的忍者數量(K), 1 ≤ K ≤ N
衛兵數量(M), 1 ≤ M ≤ 100 000

N ≤ 20，M ≤ 100 的測試資料佔分10%。
N ≤ 1 000，M ≤ 1 000 的測試資料佔分40%。

假如至少有一個灌木叢「一定有忍者」，輸出所有「一定有忍者」的灌木叢編號。灌木叢編號請由小到大輸出，每行一個編號。也就是說，如果有 X 個灌木叢「一定有忍者」，輸出就會有 X 行。假如沒有任何灌木叢「一定有忍者」，輸出-1。

Sample Input:Sample Output:

Sample Input 1:
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1

Sample Input 2:
5 1 1
1 5 1

Sample Output 1:
3
5

Sample Output 2:
-1

HINT:

在 Sample 1 中，有兩種滿足條件的忍者躲藏方式，第一個是三名忍者躲在灌木叢1、3、5 ，另一個是躲在灌木叢2、3、5。不管是哪一種躲藏方式，灌木叢3 和5 中「一定有忍者」，所以我們輸出3 和5。至於灌木叢1，第一種狀況有忍者，但第二種就沒有。因此我們不輸出1。同理，我們也不輸出2。

Source:

APIO 2012

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	2000ms	262144kb
0-2	2000ms	262144kb
1-1	2000ms	262144kb	10
1-2	2000ms	262144kb
1-3	2000ms	262144kb
1-4	2000ms	262144kb
1-5	2000ms	262144kb
1-6	2000ms	262144kb
1-7	2000ms	262144kb
1-8	2000ms	262144kb
1-9	2000ms	262144kb
1-10	2000ms	262144kb
2-1	2000ms	262144kb	10
2-2	2000ms	262144kb
2-3	2000ms	262144kb
2-4	2000ms	262144kb
2-5	2000ms	262144kb
3-1	2000ms	262144kb	10
3-2	2000ms	262144kb
3-3	2000ms	262144kb
3-4	2000ms	262144kb
3-5	2000ms	262144kb
4-1	2000ms	262144kb	10
4-2	2000ms	262144kb
4-3	2000ms	262144kb
4-4	2000ms	262144kb
4-5	2000ms	262144kb
5-1	2000ms	262144kb	15
5-2	2000ms	262144kb
5-3	2000ms	262144kb
6-1	2000ms	262144kb	15
6-2	2000ms	262144kb
6-3	2000ms	262144kb
6-4	2000ms	262144kb
6-5	2000ms	262144kb
7-1	2000ms	262144kb	15
7-2	2000ms	262144kb
7-3	2000ms	262144kb
7-4	2000ms	262144kb
7-5	2000ms	262144kb
8-1	2000ms	262144kb	15
8-2	2000ms	262144kb
8-3	2000ms	262144kb
8-4	2000ms	262144kb
8-5	2000ms	262144kb