eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Охрана

Охрана

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Королевство APIO атаковано ниндзя. ниндзя очень опасны, потому что во время атаки они прячутся в тени и другие люди не видят их. Всё королевство, кроме замка APIO, где живёт король, было захвачено. Перед замком расположен ряд из n кустов. Кустарники пронумерованы от 1 до n, и в k из них спрятались k ниндзя. В замке m охранников. i-й охранник наблюдает за последовательностью кустов от a_i-го до b_i-го. Каждый охранник сообщает королю, прячутся ли ниндзя в последовательности кустов, за которой он наблюдает. Вы, как слуга короля, должны сказать ему, основываясь на этих отчётах, в каких кустах "определённо" прячется ниндзя. Нидзя "определённо" прячется в кусте, если он в нём прячется в любом возможном расположении ниндзя, которые не противоречат отчётам охранников.

Задание

Напишите программу, которая, имея информацию об охранниках и их отчёты определит все кусты, где "определённо" прячется ниндзя.

Ограничения

1n100000 - Количество кустов 1kn - Количество ниндзя 1m 100000 - Количество охранников

Входные данные

Первая строка содержит три целых числа n, k, m, где n - количество кустов, k - количество ниндзя и m - количество охранников. Следующие m строк содержат информацию об охранниках и их отчёты. i-я строка содержит три разделённых пробелами целых числа a_i, b_i, c_i (a_ib_i), обозначающие, что i-й охранник наблюдает за кустами от a_i до b_i. c_i может быть 0 или 1. Если c_i = 0, то в кустах от a_i до b_i нет ниндзя. Если c_i = 1, то в кустах от a_i до b_i есть хотя бы один ниндзя.

Для каждого теста гарантируется, что существует как минимум одна расстановка ниндзя, которая не противоречит отчётам охранников.

Выходные данные

Если есть кусты, в которых "определённо" прячется ниндзя, выведите номера этих кустов на стандартный поток вывода. Номера кустов должны быть записаны в возрастающем порядке и каждая строка должна содержать ровно одно число. То есть, если в x кустах "определённо" прячется ниндзя, вывод должен состоять из x строк. Если нет таких кустов, выведите '-1'.

Примечания к примерам

В 1-м примере существует две возможные расстановки ниндзя, удовлетворяющие условиям: 3 ниндзя прячутся в кустах 1, 3, 5, или 3 ниндзя прячутся в кустах 2, 3, 5.

Так как ниндзя прячутся в кустах 3 и 5 во всех возможных расстановках, нужно вывести 3 и 5. Рассматривая же куст 1, можно заметить, что существует расстановка, в которой ниндзя прячется в нём, но также существует расстановка, в которой ниндзя не прячется в нём, поэтому не нужно выводить 1. По той же причине не следует выводить 2.

Во 2-м примере нет кустов, в которых "определённо" прячется ниндзя, поэтому нужно вывести '-1'.

Пример

Входные данные #1
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
Выходные данные #1
3
5
Источник 2012 Asia-Pacific Informatics Olympiad (APIO), Problem B