This summer, Antun and Branka stumbled upon a very interesting beach, which was completely covered with plastic 'pebbles' brought by the sea from the containers that fell from the cargo ships. They decided to take back with them ~n~ of these pebbles, some red and some blue. Now that autumn has arrived, they are playing with the pebbles and reminiscing about the warm summer days.
Their game proceeds as follows: in the beginning, they place the ~n~ pebbles in a row. Then, Antun and Branka make moves in turn, each time removing one of the pebbles from one of the ends of the row, until someone obtains ~k~ red pebbles, losing the game. Antun moves first and is wondering whether he could win regardless of the moves Branka makes. Please help him and write a program which will answer his question.
|1||10||~1 \le n \le 20~|
|2||20||~1 \le n \le 50~|
|3||40||~1 \le n \le 350~|
The first line contains two integers, ~n~ and ~k~ ~(1 \le k < n \le 350)~.
The second line contains a sequence of ~n~ characters
C denotes a red pebble, and
P denotes a
blue pebble. The character
C appears at least ~2k-1~ times.
If Antun can win regardless of Branka's moves, you should print
DA; otherwise, print
Sample Input 1
4 1 CCCP
Sample Output 1
Sample Input 2
8 2 PCPPCCCC
Sample Output 2
Explanation for Sample Output 2
Antun can take a blue pebble from the left (
CPPCCCC). Then, Branka has to take a red pebble.
If she takes a pebble from the left (
PPCCCC), Antun will take the first, and Branka the second blue pebble
on the left, after which only red pebbles remain and Branka will lose.
If she takes a pebble from the right (
CPPCCC), Antun can take another pebble from the right and then
Branka will again have to take another red pebble and lose.
Sample Input 3
9 1 PPCPPCPPC
Sample Output 3