Mirko 觉得很无聊，于是他拿了一张纸，写下了一个长度为 $N$ 的序列 $A$，该序列恰好包含 $1$ 到 $N$ 之间的每个正整数各一次。之后，他又拿了另一张纸，写下了关于序列 $A$ 的 $M$ 条描述。

每条描述具有以下格式之一：

• 1 $x$ $y$ $v$ — 位置在 $x$ 到 $y$（含）之间的最大值等于 $v$
• 2 $x$ $y$ $v$ — 位置在 $x$ 到 $y$（含）之间的最小值等于 $v$

接着 Slavko 走了过来，看到并偷走了第一张纸。Mirko 非常绝望，他请求你找出一个符合这些描述的序列，该序列不一定与原序列完全相同。

输入格式

第一行包含两个正整数 $N$（$1 \le N \le 200$），表示序列的长度，和 $M$（$0 \le M \le 40\,000$），表示描述的数量。

接下来的 $M$ 行，每行包含一条如上所述的描述。

输出格式

输出的第一行也是唯一一行应包含 $N$ 个空格分隔的正整数（满足所有描述，且包含 $1$ 到 $N$ 的所有正整数），如果不存在这样的序列，则输出 -1。

样例

输入样例 1

3 2
1 1 1 1
2 2 2 2

输出样例 1

1 2 3

输入样例 2

4 2
1 1 1 1
2 3 4 1

输出样例 2

-1

输入样例 3

5 2
1 2 3 3
2 4 5 4

输出样例 3

1 2 3 4 5