Vương quốc APIO đang bị ninja tấn công. Trước lâu đài có một hàng gồm \(N\) bụi cây, đánh số từ \(1\) đến \(N\). Có đúng \(K\) ninja ẩn trong đúng \(K\) bụi cây khác nhau.

Có \(M\) lính canh. Lính canh \(i\) quan sát đoạn bụi cây từ \(A_i\) đến \(B_i\) và báo rằng trong đoạn mình quan sát có ninja hay không. Dựa trên tất cả báo cáo, bạn phải xác định những bụi cây mà chắc chắn có ninja ẩn nấp. Một bụi cây được xem là chắc chắn có ninja nếu nó có ninja trong mọi cách bố trí \(K\) ninja không mâu thuẫn với các báo cáo.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,K,M\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i\) với \(A_i\le B_i\) và \(C_i\in\{0,1\}\):
• \(C_i=0\): không có ninja nào trong các bụi từ \(A_i\) đến \(B_i\).
• \(C_i=1\): có ít nhất một ninja trong các bụi từ \(A_i\) đến \(B_i\).

Dữ liệu bảo đảm tồn tại ít nhất một cách bố trí ninja phù hợp với mọi báo cáo.

Dữ liệu ra

Nếu có bụi cây chắc chắn chứa ninja, in số hiệu các bụi đó theo thứ tự tăng dần, mỗi số trên một dòng. Nếu không có bụi nào như vậy, in -1.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le K\le N\).
• \(1\le M\le 100\,000\).

Ví dụ

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

3
5

5 1 1
1 5 1

-1

Giải thích

Trong ví dụ thứ nhất có hai cách bố trí phù hợp: ninja ở các bụi \(1,3,5\) hoặc ở các bụi \(2,3,5\). Vì bụi \(3\) và \(5\) có ninja trong cả hai cách nên phải in 3 và 5.

Trong ví dụ thứ hai, không có bụi cây nào chắc chắn chứa ninja.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Guard.