Probe

Several special objects are buried somewhere along a straight road. Think of the road as a one-dimensional array of length $K$. Each unit cell either holds one object (#) or is empty (-). In the picture below the numbers are the cell indices, and a cell marked with ▲ contains an object.

Figure 1

You may inspect how many objects lie in a contiguous range using the query Probe[x, y]. If the range from $x$ to $y$ contains $r$ objects, we write Probe[x, y] = r (with $x \le y$). For example, in Figure 1 we have Probe[2, 7] = 3, Probe[2, 2] = 0, Probe[6, 9] = 4, and Probe[5, 12] = 5.

Write a program that reconstructs an arrangement of objects on the road that satisfies all of the given probe results simultaneously.

The first line contains two integers $K$ and $N$. $K$ is the length of the whole range and $N$ is the number of probe results. Each of the next $N$ lines contains one probe result as three space-separated integers $x$ $y$ $r$, meaning Probe[x, y] = r.

Constraints: $3 \le K \le 40$, $2 \le N \le 1000$, $1 \le x \le y \le K$, $0 \le r \le 1000$.

Print an arrangement satisfying every probe result as a string of length $K$, using # for a cell that holds an object and - for an empty cell. If several arrangements satisfy all the results, print the lexicographically smallest such string (compared character by character, where # comes before -). If no arrangement satisfies all the probe results, print NONE.