Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D1T2。$\texttt{4s,0.5G}$。

Acknowledgement: SPJ by

Problem Description

You are painting on a wooden board of length $N\,\mathrm{m}$。The board is divided from left to right into $N$ cells, and each cell is $1\,\mathrm{m}$ long。

It is known that $M$ strokes were painted on the board。The $i$-th stroke paints cells $l_i\sim r_i$ into color $c_i$。

Given the final state of the board after all painting, construct an order of operations such that after performing the operations once, the board becomes exactly the given final state, or report that there is no solution。

Input Format

The first line contains two positive integers $N,M$。

The next $M$ lines each contain three integers $l_i,r_i,c_i$, describing a painting operation。

The next line contains $N$ integers。The $i$-th integer denotes the final color $b_i$ of the $i$-th cell。In particular, if $b_i=0$, it means the cell with $b_i$ is unpainted.

Output Format

If there is no solution, output $\texttt{NE}$ (Croatian for “No”)。

Otherwise, output $\texttt{DA}$ (Croatian for “Yes”) on the first line; on the second line output a permutation of $1\sim M$ indicating the painting order。

If there are multiple solutions, any one is acceptable。

6 5
3 5 5
1 1 6
1 3 2
1 4 7
4 6 6
6 2 5 5 5 6

DA
4 5 3 1 2

14 6
6 9 4
12 13 6
2 3 5
1 14 3
5 6 9
9 12 8
3 5 5 3 9 4 4 4 8 8 8 6 6 3

DA
4 5 1 6 2 3

15 5
7 8 3
10 14 5
4 7 2
3 12 1
5 9 4
0 0 1 2 4 4 3 3 4 5 1 1 5 5 0

NE

Hint

For $100\%$ of the testdata, it is guaranteed that:

• $1\le N,M\le 5\times 10^5$；
• $1\le l_i\le r_i\le N$；
• $1\le c_i\le 5\times 10^5$；
• $0\le b_i\le 5\times 10^5$。

• Special property A: all $c_i$ are pairwise distinct。
• Special property B: $1\le c_i\le 5$。

Translated by ChatGPT 5