Problem Description

Alice and Bob are playing a game again.

In front of them, there are $n$ stones in a row. Each stone is either red or blue.

Alice moves first. On each turn, a player chooses one end and takes one stone from that end. Whoever takes $k$ red stones first loses.

Assuming both Alice and Bob play optimally, determine who will win in the end.

Input Format

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

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

Output Format

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

4 1
CCCP

DA

8 2
PCPPCCCC

DA

9 1
PPCPPCPPC

NE

Hint

Constraints

For all testdata, $1 \le k < n \le 350$, and red stones appear at least $2k-1$ times.

Notes

The total score of this problem is $70$ points.

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

Translated by ChatGPT 5