题目描述

本题中下标是 $\texttt{\textcolor{red}{0-indexed}}$ 的。

构造一个长度为 $n$ 的 $\text{01}$ 串 $a_0\sim a_{n-1}$，满足以下条件：

• $\forall 0\le i\lt m$，都有 $k_i\mathrm{thmin}(a_{l_i},a_{{l_i}+1},\ldots,a_{r_i})=\mathrm{val}_i$。

这里，$k\mathrm{thmin}$ 表示一个数列内第 $k$ 小的元素。

输入格式

第一行，两个正整数 $n,m$。

接下来 $m$ 行，第 $i$ 行四个非负整数 $l_{i-1},r_{i-1},k_{i-1},\mathrm{val}_{i-1}$。

输出格式

如果有解，直接输出对应的 $01$ 串（元素中间要加空格）。

否则输出一行一个 $\texttt{-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

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 5\times 10^3$；
• $1\le m\le 10^4$；
• $0\le l_i\le r_i\lt n$；
• $1\le k_i\le r_i-l_i+1$；
• $\mathrm{val}_i\in \{0,1\}$。

子任务

• 特殊性质 $\text{A}$：$\forall 0\le i\lt m$，$k_i=1$。
• 特殊性质 $\text{B}$：$\forall 0\le i\lt m$，要么 $k_i=1$，要么 $k_i=r_i-l_i+1$。