Зворотний запит мінімального значення в діапазоні
Обернені задачі — це динамічно розвиваючася галузь у комп'ютерних науках. На відміну від традиційних задач, де, маючи деякі дані D, необхідно вирішити задачу оптимізації або обчислення P, в оберненій задачі вам дано задачу P і результат R оптимізації/обчислення. Ваше завдання — відновити початкові дані D. У цій задачі вам належить вирішити обернену задачу мінімального запиту на діапазон.
Розглянемо масив a[1..n]. Відповідь на мінімальний запит на діапазон Q(i, j) — це мінімальне значення серед a[i], ..., a[j]. Вам дано n і серію мінімальних запитів на діапазон з відповідями. Відновіть початковий масив a.
Вхідні дані
Перший рядок вхідного файлу містить n — розмір масиву, і m — кількість запитів (1 ≤ n, m ≤ 100000). Наступні m рядків містять по три цілих числа: i, j і q, що означають, що Q(i, j) = q (1 ≤ i ≤ j ≤ n, -2^31 ≤ q ≤ 2^31-1).
Вихідні дані
Якщо дані у вхідному файлі неконсистентні, тобто не існує такого масиву a, виведіть "inconsistent" у першому рядку вихідного файлу.
В іншому випадку виведіть "consistent" у першому рядку вихідного файлу. Другий рядок повинен містити масив. Елементи масиву повинні бути цілими числами від -2^31 до 2^31-1. Якщо існує декілька рішень, виведіть будь-яке з них.