Inverse Range Minimum Query#3080
Inverse problems are a rapidly growing area in computer science. Unlike traditional problems where, given some data , you are to solve an optimization or calculation problem , in the inverse problem you are given a problem and the result of this optimization or calculation. Your task is to restore the original data . In this problem, you are asked to solve the inverse range minimum query problem.
Consider an array . The answer to a range minimum query Q(i, j) is the minimum value among a_i, \ldots, a_j. You are given and several range minimum queries with their answers. Restore the original array .
The first line contains , the size of the array, and , the number of queries (1 \le n, m \le 100000). Each of the next lines contains three integers: , , and meaning Q(i, j) = q (1 \le i \le j \le n, -2^{31} \le q \le 2^{31}-1).
If the input data are inconsistent, i.e., if there is no such array , output "inconsistent" on the first line of the output.
Otherwise, output "consistent" on the first line. The second line must contain the array. The elements of the array must be integers from -2^{31} to 2^{31}-1. If there are several solutions, output any one.
Exemplul 1