你的任务是确定一个长度为 $N$ 的二进制数组 $A$，使其满足 $M$ 个给定约束，约束形式如下： $(l, r, k, \text{value})$ - 子数组 $A[l..r]$ 中第 $k$ 小的元素为 $\text{value}$ ($0 \le l \le r < N, 1 \le k \le r - l + 1, 0 \le \text{value} \le 1$)。请注意，数组 $A$ 的下标从 $0$ 开始。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 5\,000, 1 \le M \le 10\,000$)，分别表示数组 $A$ 的长度和约束的数量。

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

输出格式

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

子任务

(1) $1 \le N \le 18, 1 \le M \le 200$ (7 分) (2) $1 \le N \le 5\,000, 1 \le M \le 10\,000$，对于所有约束，$k = 1$ 成立 (13 分) (3) $1 \le N \le 5\,000, 1 \le M \le 10\,000$，对于所有约束，$k = 1$ 或 $k = (r - l + 1)$ 成立 (25 分) (4) $1 \le N \le 5\,000, 1 \le M \le 10\,000$ (55 分)

样例

输入 1

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

输出 1

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$。