| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 15 | 4 | 4 | 57.143% |
Во Всеберляндской олимпиаде по программированию принимают участие $n$ человек, пронумерованных последовательными целыми числами от $1$ до $n$.
По итогам соревнований участники показали различные результаты и расположились в некотором порядке. Все участники заняли различные места от $1$ до $n$, место $i$ занял участник с номером $a_i$. Только вот из-за непредвиденного сбоя результаты соревнований были безвозвратно утрачены.
Однако выяснилось, что пока таблица ещё была доступна, два члена жюри независимо сделали пометки относительно результатов тура.
Первый член жюри сделал $c_1$ записей вида <<среди участников, занявших места с $l_i$ по $r_i$ включительно, наименьший номер участника равен $m_i$>>.
Второй член жюри сделал $c_2$ записей вида <<среди участников, занявших места с $L_i$ по $R_i$ включительно, наибольший номер участника равен $M_i$>>.
По имеющимся записям требуется восстановить положение участников $a_1, a_2, \ldots, a_n$ или же сообщить, что в записях допущена ошибка.
Если вариантов положения участников несколько, жюри хочет восстановить такое, в котором последовательность $a_1, a_2, \ldots, a_n$ лексикографически минимальна.
Первая строка входных данных содержит три целых числа $n$, $c_1$ и $c_2$ --- количество участников, количество записей, сделанных первым членом жюри, и количество записей, сделанных вторым членом жюри, соответственно ($1 \leq n \leq 50; 0 \leq c_1 + c_2 \leq 50$).
Последующие $c_1$ строк задают записи, сделанные первым членом жюри. Каждая такая запись содержит по три целых числа $l_i$, $r_i$ и $m_i$ ($1 \le l_i \le r_i \le n$; $1 \le m_i \le n$).
Последующие $c_2$ строк задают записи, сделанные вторым членом жюри, в аналогичном формате.
Если данные противоречивы, выведите $-1$. Иначе выведите $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- положение участников, удовлетворяющее всем записям и пожеланию жюри, где $a_i$ --- это номер участника, занявшего $i$-е место.
4 1 1 1 2 2 3 4 3
2 4 1 3
4 1 1 1 3 2 1 3 1
-1
4 1 0 1 4 2
-1