0005 - 見張り

APIO 国は忍者の襲撃を受けている．物陰に隠れ敵の見えないところから攻撃する忍者はとても強く，国王の住む APIO 城を残してすべてが攻め落とされてしまった．今，APIO 城の前には N 個の茂みが１列に並んでいる．茂みには 1, . . . , N の番号が順番についており，その中のちょうど K 個に K 人の忍者が隠れている．APIO 城には見張りが M 人おり，見張り i は茂み A_i から B_i を見張っている．今，それぞれの見張りは自分の見張っている茂みに忍者が隠れていたかどうかを国王に報告した．国王に仕えているあなたは，そ の情報を元に，“確実に忍者が隠れていると言える” 茂みがどれであるか国王に伝えなければならない．ただし，ある茂みに “確実に忍者が隠れていると言える” とは，見張りたちの報告と矛盾しないすべての忍者の配置において，その茂みに忍者が隠れているということである．

課題

見張りの情報と見張りからの報告の情報が与えられたとき，“確実に忍者が隠れていると言える” 茂みをすべて求めるプログラムを作成せよ．

制限

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数 N, K, M が空白を区切りとして書かれている．N は茂みの数を，K は隠れている忍者の人数を，M は見張りの人数を表す．
• 続く M 行には，見張りの情報と見張りからの報告の情報が書かれている．これらの行のうちの i 行目には整数 A_i, B_i, C_i (Ai ≦ B_i) が空白を区切りとして書かれている．A_i, B_i は見張り i の見張っている茂みが A_i から B_i であることを表す．C_i は 0 または 1 である．Ci が 0 である場合，茂み A_i から B_iには忍者は隠れておらず，C_i が 1 である場合，茂み A_i から B_i のうちの１つ以上に忍者が隠れている．
  また，すべての入力について，見張りたちの報告と矛盾しない忍者の配置が１つ以上存在する．

出力

“確実に忍者が隠れていると言える”茂みが存在する場合，標準出力に，“確実に忍者が隠れていると言える” 茂みを表す番号を昇順に改行区切りですべて出力せよ．“確実に忍者が隠れていると言える” 茂みを X個とすると，出力は X 行からなる．“確実に忍者が隠れていると言える” 茂みが存在しない場合，標準出力に −1 を１行で出力せよ．

採点基準

採点用データのうち，配点の 10%分については，N ≦ 20，M ≦ 100 を満たす．

採点用データのうち，配点の 50%分については，N ≦ 1 000，M ≦ 1 000 を満たす．

入出力の例

入力例1

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

出力例1

3
5

この入力例において，条件を満たす忍者の配置は，茂み 1, 3, 5 と茂み 2, 3, 5 の 2 通りである．２つの配置のどちらでも茂み 3, 5 には忍者が隠れているので，3 と 5 を出力する．茂み 1, 2 には忍者が隠れている配置があるが，隠れていない配置もあるため，1 と 2 は出力しない．

入力例2

5 1 1
1 5 1

出力例2

-1

この場合，“確実に忍者が隠れていると言える”茂みは存在しないので，−1 を出力する．