题目背景

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

鸣谢：SPJ by

题目描述

在一块长 $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$ 的排列表示涂色顺序。

若有多解，任意均可。

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

提示

对于 $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$。

• 特殊性质 A：$c_i$ 两两不同。
• 特殊性质 B：$1\le c_i\le 5$。