2021 COCI Round #1, October 16


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.


The first line contains two integers n and k (1k < n350). The second line contains a sequence of n characters C or P, where C denotes a red pebble, and P denotes a blue pebble. The character C appears at least 2 * k1 times.


If Antun can win regardless of Branka’s moves, you should print DA, otherwise print NE.

Time limit 1 second
Memory limit 256 MiB
Input example #1
4 1
Output example #1
Input example #2
8 2
Output example #2
Input example #3
9 1
Output example #3
Source 2021 COCI Croatian Open Competition In Informatics, Round 1, October 16