Обратный запрос минимального значения в диапазоне
Обратные задачи — это динамично развивающаяся область в компьютерных науках. В отличие от традиционных задач, где, имея некоторые данные 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. Если существует несколько решений, выведите любое из них.