Problem Description

Alice and Bob are playing a game again.

In front of them, there are $n$ stones arranged in a row, with two colors: red and blue.

Alice moves first, and each player, in their turn, chooses one end from which to take a stone. The player who first takes $k$ red stones loses the game.

Assuming both Alice and Bob are extremely intelligent, determine who will win the game.

Input Format

The first line contains two integers $n$ and $k$.

The next line contains a string of length $n$, consisting only of characters C and P, where C represents a red stone and P represents a blue stone.

Output Format

If Alice is guaranteed to win, output DA; otherwise, output NE.

Sample Input and Output

Sample Input #1

4 1
CCCP

Sample Output #1

DA

Sample Input #2

8 2
PCPPCCCC

Sample Output #2

DA

Sample Input #3

9 1
PPCPPCPPC

Sample Output #3

NE

Notes

Data Range

For all data, $1 \le k < n \le 350$, and there are at least $2k-1$ red stones.

Notes

This problem is worth a total of 70 points.

This problem is translated from the Croatian Open Competition in Informatics 2021/2022 Contest #1 T2 Kamenčići.

见题面 Input 部分

见题面 Output 部分