题目描述

题目译自 Romanian Master of Informatics 2019 Day1 T3 「Restore Array」

你的任务是根据 $M$ 个给定的约束条件，确定一个长度为 $N$ 的二进制数组 $A$。每个约束条件的形式为：$(l, r, k, \text{value})$ ($0 \leq l \leq r < N$, $1 \leq k \leq r-l+1$, $0 \leq \text{value} \leq 1$)，表示子数组 $A[l\ldots r]$ 中第 $k$ 小的元素是 $\text{value}$。请注意，数组 $A$ 的编号从 $0$ 开始。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ ($1 \leq N \leq 5000$, $1 \leq M \leq 10000$)，表示数组 $A$ 的长度和约束条件的数量。

接下来的 $M$ 行描述了这些约束条件。每行包含四个整数 $l_i, r_i, k_i, \text{value}_i$，描述第 $i$ 个约束。

输出格式

输出的第一行包含 $N$ 个整数，表示一个可能的二进制数组 $A$。如果存在多个符合所有 $M$ 个约束条件的数组，你可以输出其中任意一个。如果不存在这样的数组，则输出单个整数 $-1$。

样例

输入

4 5
0 1 2 1
0 2 2 0
2 2 1 0
0 1 1 0
1 2 1 0

输出

0 1 0 0

存在多个二进制数组能够满足所有约束条件，其中一个是 0 1 0 0，原因如下：

• 在子数组 [0, 1] 中，第 $2$ 小的元素是 $1$。
• 在子数组 [0, 1, 0] 中，第 $2$ 小的元素是 $0$。
• 在子数组 [0] 中，第 $1$ 小的元素是 $0$。
• 在子数组 [0, 1] 中，第 $1$ 小的元素是 $0$。
• 在子数组 [1, 0] 中，第 $1$ 小的元素是 $0$。

数据范围与提示

详细子任务附加限制及分值如下表所示。