Painting Sequence Reconstruction

You are given a wooden board of length $N$ meters which is divided into $N$ consecutive cells (each of length $1$ meter). There are $M$ painting strokes. The $i$-th stroke paints cells from $l_i$ to $r_i$ (inclusive) with color $c_i$. After all the strokes have been applied (in some unknown order), the final board state is given as a string of length $N$, where the $j$-th character represents the final color on cell $j$ (the colors are represented as digits or characters).\n\nYour task is to determine a permutation (an ordering) of the $M$ strokes such that there exists a moment (right after performing a certain prefix of the operations) at which the board state is exactly the given final state. (In the solution below, we will ensure that when all strokes are applied in the computed order the board is exactly as given.) If no valid ordering exists, output -1.\n\nNote that if a stroke is applied, it completely overwrites the colors of all cells in its interval. Thus, if an interval of the final board state is homogeneous (i.e. a maximal contiguous segment having the same color), then there must be at least one stroke which exactly matches that segment’s boundaries and color. We call such a stroke a mandatory stroke. A valid ordering can be constructed by placing all non‐mandatory strokes first (in any order) and then, in left-to-right order of the board, placing the corresponding mandatory strokes to finalize each segment.

inputFormat

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 10^5$).\nThe second line contains a string of length $N$ representing the final board state.\nEach of the following $M$ lines contains two integers $l_i$ and $r_i$ and a color $c_i$, where $1 \le l_i \le r_i \le N$. The color $c_i$ is given as a single character or digit. It is guaranteed that every cell in the final state has been painted by at least one stroke.

outputFormat

If a valid ordering exists, output a single line containing $M$ integers—a permutation of the strokes (indexed from $1$ to $M$) representing the order in which the strokes are applied such that after applying all strokes the board state is exactly the given state. (Note that in your ordering, there is a moment right after applying a prefix of the operations in which the board state matches the given state.)\nIf no valid ordering exists, output -1.

sample

5 5
12233
1 1 1
1 3 1
2 3 2
4 5 3
2 5 2

2 5 1 3 4