题目描述

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

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

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ $(1 \leq N \leq 5000,1 \leq M \leq 10000)$，表示数组 $A$ 的长度和约束条件的数量。 接下来的 $m$ 行描述了这些约束条件。每行包含四个整数 $l_i, r_i, k_i, 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，原因如下：

1. 在子数组 0 1 0 0 中，第 $2$ 小的元素是 1。
2. 在子数组 0 1 0 0 中，第 $2$ 小的元素是 0。
3. 在子数组 0 1 0 0 中，第 $1$ 小的元素是 0。
4. 在子数组 0 1 0 0 中，第 $1$ 小的元素是 0。
5. 在子数组 0 1 0 0 中，第 $1$ 小的元素是 0。

数据范围与提示

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