Restore the Sequence

There is a sequence A of length N. A is a permutation of the integers from 1 to N, so every integer in that range appears exactly once.

You are given M descriptions of A. Each description has one of the following forms.

• 1 x y v: the maximum value among the x-th through y-th elements of A is v.
• 2 x y v: the minimum value among the x-th through y-th elements of A is v.

Find and print one original sequence A that satisfies every description. If more than one sequence satisfies the descriptions, any one of them may be printed.

The first line contains the sequence size N and the number of descriptions M.

1 <= N <= 200, 0 <= M <= 40000

Each of the next M lines contains one description in the form 1 x y v or 2 x y v.

Print N integers on the first line: a sequence A that satisfies all descriptions.

If no such sequence exists, print -1.