Охорона#3385

Охорона

1 секунда

256 мегабайтів

Легка

Королівство APIO зазнало нападу ніндзя. Ці ніндзя дуже небезпечні, оскільки під час атаки вони ховаються в тіні, і їх не видно. Все королівство, окрім замку APIO, де мешкає король, було захоплено. Перед замком розташовано ряд з $n$ кущів, пронумерованих від $1$ до $n$ . У $k$ з цих кущів сховалися $k$ ніндзя. У замку є $m$ охоронців. $i$ -й охоронець спостерігає за ділянкою кущів від $a_{i}$ a_i-го до $b_{i}$ b_i-го. Кожен охоронець повідомляє королю, чи є ніндзя в ділянці кущів, яку він охороняє. Ваше завдання, як слуги короля, полягає в тому, щоб визначити, на основі цих звітів, в яких кущах "безумовно" ховається ніндзя. Ніндзя "безумовно" ховається в кущі, якщо він там перебуває у всіх можливих розташуваннях, які не суперечать звітам охоронців.

Напишіть програму, яка, використовуючи інформацію про охоронців та їх звіти, визначить усі кущі, де "безумовно" ховається ніндзя.

$1 \leq n \leq 100000$ 1 \le n \le 100000 - Кількість кущів

$1 \leq k \leq n$ 1 \le k \le n - Кількість ніндзя

$1 \leq m \leq 100000$ 1 \le m \le 100000 - Кількість охоронців

Вхідні дані

Перший рядок містить три цілі числа $n$ , $k$ , $m$ , де $n$ - кількість кущів, $k$ - кількість ніндзя, а $m$ - кількість охоронців. Наступні $m$ рядків містять інформацію про охоронців та їх звіти. $i$ -й рядок містить три цілі числа, розділені пробілами: $a_{i}$ a_i, $b_{i}$ b_i, $c_{i}$ c_i ( $a_{i} \leq b_{i}$ a_i \le b_i), що означають, що $i$ -й охоронець спостерігає за кущами від $a_{i}$ a_i до $b_{i}$ b_i. $c_{i}$ c_i може бути $0$ або $1$ . Якщо $c_{i} = 0$ c_i = 0, то в кущах від $a_{i}$ a_i до $b_{i}$ b_i немає ніндзя. Якщо $c_{i} = 1$ c_i = 1, то в кущах від $a_{i}$ a_i до $b_{i}$ b_i є хоча б один ніндзя.

Для кожного тесту гарантується, що існує принаймні одне розташування ніндзя, яке не суперечить звітам охоронців.

Вихідні дані

Якщо є кущі, в яких "безумовно" ховається ніндзя, виведіть номери цих кущів на стандартний потік виводу. Номери кущів повинні бути записані у зростаючому порядку, і кожен рядок повинен містити рівно одне число. Тобто, якщо в $x$ кущах "безумовно" ховається ніндзя, вивід повинен складатися з $x$ рядків. Якщо таких кущів немає, виведіть '-1'.

Приклади

Приклад 1

Примітка

У $1$ -му прикладі існує два можливих розташування ніндзя, що задовольняють умови: $3$ ніндзя ховаються в кущах $1$ , $3$ , $5$ , або $3$ ніндзя ховаються в кущах $2$ , $3$ , $5$ .

Оскільки ніндзя ховаються в кущах $3$ і $5$ у всіх можливих розташуваннях, потрібно вивести $3$ і $5$ . Розглядаючи ж кущ $1$ , можна помітити, що існує розташування, в якому ніндзя ховається в ньому, але також існує розташування, в якому ніндзя не ховається в ньому, тому не потрібно виводити $1$ . З тієї ж причини не слід виводити $2$ .

У $2$ -му прикладі немає кущів, в яких "безумовно" ховається ніндзя, тому потрібно вивести '-1'.