Дим над водою#4337

Дим над водою

2 секунди

256 мегабайтів

Легка

Вздовж берега Міссісіпі стоїть $n$ вігвамів. Однієї прохолодної літньої ночі у кожному з них розпалили багаття, причому протягом усієї ночі підтримували багаття однієї і тієї ж сили.

Шаман розвідки Розсудливий Манул ходив тієї ночі досить далеко від річки. За цю ніч $m$ разів він залазив на алое, оглядаючи вігвами рідного племені, і кожного разу він бачив декілька вігвамів, які утворювали відрізок, що йшов підряд, і запам'ятовував, у якому з них стовп диму був найсильніший.

Базуючись на даних, які запам'ятав Розсудливий Манул, відновіть, які вігвами опалювали сильніше, а які слабше. Якщо декілька ситуацій підходить під опис Розсудливого Манула, виведіть довільну з них. Якщо дані суперечливі, повідомте про це Манулу.

Вхідні дані

У першому рядку вхідного файлу містяться цілі числа $n$ та $m$ — кількість вігвамів та підйомів на алое відповідно ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000, $0 \leq m \leq 100000$ 0 \leq m \leq 100000).

У кожному з наступних $m$ рядків міститься три цілих числа $l_{i}$ l_i, $r_{i}$ r_i та $p_{i}$ p_i ( $1 \leq l_{i} \leq p_{i} \leq r_{i} \leq n$ 1 \leq l_i \leq p_i \leq r_i \leq n), які означають, що серед вігвамів з $l_{i}$ l_i-го по $r_{i}$ r_i-й включно найсильніший стовп диму йшов з вігваму під номером $p_{i}$ p_i.

Вихідні дані

Якщо інформація, яку запам'ятав Манул, суперечлива, виведіть -1. У протилежному випадку виведіть $n$ різних чисел від $1$ до $n$ , де $i$ -те число відповідає стовпу диму з $i$ -го вігваму — більші числа відповідають сильнішим стовпам диму.

Приклади

Приклад 1