eolymp
bolt
Try our new interface for solving problems
Məsələlər

Inverse Range Minimum Query

Inverse Range Minimum Query

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Inverse problems represent a quickly growing area in computer science. Unlike traditional problems, where given some data D, the task is to solve some optimization or calculation problem P, in the inverse problem you are given a problem P and the result R of the optimization/calculation. You have to restore the original data D. In this problem you are asked to solve inverse range minimum query problem.

Consider an array a[1..n]. The answer to a range minimum query Q(i, j) is the minimal value among a[i], ..., a[j]. You are given n and a series of range minimum queries with answers. Restore the original array a.

Giriş verilənləri

The first line of the input file contains n - the size of the array, and m - the number of queries (1n, m100000). The following m lines contain three integer numbers each: numbers i, j and q mean that Q(i, j) = q (1ijn,-2^31q2^31-1).

Çıxış verilənləri

If data in the input file is inconsistent, i.e. no such array a exists, output "inconsistent" at the first line of the output file.

In the other case output "consistent" at the first line of the output file. The second line must contain the array. The elements of the array must be integers between -2^31 and 2^31-1. If there are several solutions, output any one.

Nümunə

Giriş verilənləri #1
3 2
1 2 1
2 3 2
Çıxış verilənləri #1
consistent
1 2 2
Müəllif Andrew Stankevich
Mənbə Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008