Constructing Binary String with (k)th Minimum Constraints

Given an integer \(n\) and \(m\) constraints, construct a binary string \(a_0, a_1, \ldots, a_{n-1}\) (0-indexed) such that for each constraint \(i\) (\(0 \le i .

It is guaranteed that there exists at least one solution.

inputFormat

The first line contains two integers \(n\) and \(m\) -- the length of the binary string and the number of constraints.

Each of the next \(m\) lines contains four integers \(l_i\), \(r_i\), \(k_i\), and \(\mathrm{val}_i\) describing a constraint. The indices are 0-indexed and \(r_i\) is inclusive.

outputFormat

Output a binary string of length \(n\) that satisfies all the given constraints. If no solution exists, output -1.

sample

3 1
0 2 2 0

001