小达沃有一天打开电视，看到一位先生画了一幅精美的肖像画。“真是天才！”达沃心想，于是他立刻抓起颜料桶和最喜欢的画笔，跑到院子里开始工作。

在院子里，他找到了一块长为 $N$ 米的木板，准备用它代替画布。随后，他 $M$ 次将画笔蘸上某种颜色 $c$，并从木板的第 $a$ 米处涂到第 $b$ 米处，将该段涂上颜色 $c$。每次涂色后，他都会在一张小纸条上记下他用什么颜色涂了木板的哪一部分。

杰作完成了，达沃非常高兴，现在他只需要制作一堆副本，在世界各地的画廊展出。幸好他把每一次笔触都记在了纸上……

什么！？风吹过，纸条全混在一起了！达沃崩溃了，请帮他确定他可能按什么顺序进行了这些笔触，从而最终得到他的杰作，或者判断这样的顺序不存在。在这种情况下，很可能是风把某张纸条吹得太远了，或者是达沃在记录时犯了错误。

输入格式

第一行包含题目描述中的自然数 $N$ 和 $M$。

接下来的 $M$ 行中，第 $i$ 行包含三个自然数 $a_i, b_i$ ($1 \le a_i \le b_i \le N$) 和 $c_i$ ($1 \le c_i \le 500\,000$)，表示达沃进行了一次笔触，将木板从第 $a_i$ 米到第 $b_i$ 米（包含）涂成了颜色 $c_i$。

最后一行包含 $N$ 个整数，其中第 $i$ 个数表示木板第 $i$ 米处的颜色。木板未涂色的部分用数字 $0$ 表示。

输出格式

如果能够以某种顺序应用达沃的笔触，使得最终产品与输入的木板颜色一致，则第一行输出单词 "DA"。否则，输出单词 "NE"。

此外，如果输出了 "DA"，则在下一行输出 $M$ 个数字，表示应用达沃笔触的顺序。其中第 $i$ 个输出的数字（记为 $p_i$）表示第 $i$ 次笔触应对应输入数据中给出的第 $p_i$ 次笔触。如果存在多种解，输出任意一种即可。

样例

输入 1

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

输出 1

DA
4 5 3 1 2

说明 1

• 开始时木板未涂色，即状态为 $(0, 0, 0, 0, 0, 0)$。
• 首先将第 $1$ 到第 $4$ 米涂上颜色 $7$，得到 $(7, 7, 7, 7, 0, 0)$。
• 然后将第 $4$ 到第 $6$ 米涂上颜色 $6$，得到 $(7, 7, 7, 6, 6, 6)$。
• 接着将第 $1$ 到第 $3$ 米涂上颜色 $2$，得到 $(2, 2, 2, 6, 6, 6)$。
• 然后将第 $3$ 到第 $5$ 米涂上颜色 $5$，得到 $(2, 2, 5, 5, 5, 6)$。
• 最后将第 $1$ 米涂上颜色 $6$，得到 $(6, 2, 5, 5, 5, 6)$。

输入 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

输出 2

DA
4 5 1 6 2 3

输入 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

输出 3

NE