INFORMAC - INFORMACIJE

Mirko was bored, so he took a piece of paper and wrote down a sequence A of length N, which contains each positive integer between 1 and N, inclusive, exactly once. After that, he took another piece of paper and wrote down M descriptions of the sequence A.

 

    Each description has one of the following formats:

1 x y v – the largest number in positions between x and y (inclusive) equals v

2 x y v – the smallest number in positions between x and y (inclusive) equals v

 

    Then Slavko came, saw, and stole the first paper. Mirko is desperate and has asked you to find some sequence matching the descriptions, not necessarily equal to the original sequence.

 

INPUT: 

    The first line of input contains two positive integers, N (1 ≤ N ≤ 200), the length of the sequence, and M (0 ≤ M ≤ 40 000), the number of descriptions.

    Each of the following M lines contains a description as described above.

 

OUTPUT:

    The first and only line of output must contain a sequence of N space-separated positive integers (matching the descriptions and containing all positive integers from 1 to N), or -1 if no such sequence exists.

 

SAMPLE TESTS:

Input

Output

3 2

1 1 1 1

2 2 2 2

 

1 2 3

4 2

1 1 1 1

2 3 4 1

 

-1

5 2

1 2 3 3

2 4 5 4

 

1 2 3 4 5


Được gửi lên bởi:Alex & Friends
Ngày:2012-12-02
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:COCI 2012-2013

hide comments
2017-05-05 16:23:17
How to AC ???
2015-12-20 17:32:51 xin đừng quên tôi
#2
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.