Little Davor turned on the TV one day and saw a gentleman drawing a beautiful portrait. "What a great talent!", Davor thought, and immediately grabbed his paint cans and his favorite brush, ran into the yard, and got to work.

In the yard, he found a board $N$ meters long that he would use instead of a canvas. Then, he dipped his brush into a paint can of color $c$ $M$ times and dragged it from the $a$-th to the $b$-th meter of the board, painting that segment with color $c$. Each time, he also wrote down on a separate piece of paper which color he used to paint which part of the board.

The masterpiece is finished, Davor is overjoyed, and now he just needs to make a bunch of copies to exhibit in all the world's galleries. It's a good thing he wrote down every brushstroke on paper...

What!? The wind blew and the papers got mixed up! Davor is heartbroken; help him determine the order in which he could have made the brushstrokes so that he ends up with his masterpiece, or conclude that such an order does not exist. In that case, the wind most likely blew away a paper too far, or Davor made a mistake while writing things down.

Input

The first line contains the natural numbers $N$ and $M$ from the problem description.

The $i$-th of the next $M$ lines contains three natural numbers $a_i, b_i$ ($1 \le a_i \le b_i \le N$) and $c_i$ ($1 \le c_i \le 500\,000$), which indicate that Davor made a brushstroke painting the part of the board from the $a_i$-th to the $b_i$-th meter (inclusive) with color $c_i$.

The last line contains $N$ integers, where the $i$-th number denotes the color with which the $i$-th meter of the board is painted. The unpainted part of the board is denoted by the number 0.

Output

In the first line, you must print the word "DA" if it is possible to apply Davor's brushstrokes in some order so that the final product matches the painted board from the input. Otherwise, you must print the word "NE".

Also, if you printed "DA", in the next line you must print $M$ numbers that indicate the order in which Davor's strokes should be applied. The $i$-th printed number (let's denote it by $p_i$) tells us that the $i$-th brushstroke should correspond to the $p_i$-th stroke listed in the input. If there are multiple solutions, print any one.

Subtasks

Examples

Input 1

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

Output 1

DA
4 5 3 1 2

Input 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

Output 2

DA
4 5 1 6 2 3

Input 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

Output 3

NE

Note

Explanation of the first example:

• At the beginning, the board is unpainted, i.e., its state is $(0, 0, 0, 0, 0, 0)$.
• First, we paint from the 1st to the 4th meter with color 7 and get $(7, 7, 7, 7, 0, 0)$.
• Then, we paint from the 4th to the 6th meter with color 6 and get $(7, 7, 7, 6, 6, 6)$.
• Then, we paint from the 1st to the 3rd meter with color 2 and get $(2, 2, 2, 6, 6, 6)$.
• Then, we paint from the 3rd to the 5th meter with color 5 and get $(2, 2, 5, 5, 5, 6)$.
• Finally, we paint the first meter with color 6 and get $(6, 2, 5, 5, 5, 6)$.