P11024 [COTS 2020] 定序 Redoslijed

译自 [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D1T2。$\texttt{4s,0.5G}$。 鸣谢：SPJ by @[mygr](https://www.luogu.com.cn/user/739552)

在一块长 $N\,\mathrm{m}$ 的木板上画画。木板被从左往右划分成 $N$ 个格子，每个格子长 $1\,\mathrm{m}$。 现在已知在木板上涂了 $M$ 笔，第 $i$ 笔将第 $l_i\sim r_i$ 个格子涂成颜色 $c_i$。 给定最后涂色后木板的状态，试构造一种操作顺序使得一次操作后木板的状态为给定状态，或报告无解。

第一行，两个正整数 $N,M$。 接下来 $M$ 行，每行三个整数 $l_i,r_i,c_i$，描述一个涂色操作。 接下来一行，$N$ 个整数，第 $i$ 个整数表示第 $i$ 个格子最后的颜色 $b_i$。**特别地，若 $b_i=0$，代表 $b_i$ 未被着色。**

如果无解，输出 $\texttt{NE}$（克罗地亚语「否」）。 否则第一行输出 $\texttt{DA}$（克罗地亚语「是」）；第二行输出一个 $1\sim M$ 的排列表示涂色顺序。 若有多解，任意均可。

对于 $100\%$ 的数据，保证： - $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$。 | 子任务编号 | $N\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $9$ | |$ 5 $ | | $ 2 $ | $5\,000$ | A |$ 10 $ | | $ 3 $ | $5\times 10^5$ | A |$ 25 $ | | $ 4 $ | $5\, 000$ || $ 12 $ | | $ 5 $ | $5\times 10^5$ | B| $ 16 $ | | $ 6 $ | $5\times 10^5$ || $ 32 $ | - 特殊性质 A：$c_i$ 两两不同。 - 特殊性质 B：$1\le c_i\le 5$。