题目描述

Alice 和 Bob 又在玩游戏。

在他们面前有 $n$ 块石头排成一行，石头有红和蓝两种颜色。

Alice 先手，每次每人从两端选择一端取出一块石头，谁先取出 $k$ 块红色石头谁输掉。

假设 Alice 和 Bob 都是绝顶聪明的，求出最后谁获胜。

输入格式

第一行为两个整数 $n,k$。

接下来一行一个长度为 $n$ 的字符串，仅由 C 和 P 组成，C 表示红色石头，P 表示蓝色石头。

输出格式

如果 Alice 必胜，输出 DA，否则输出 NE。

4 1
CCCP

DA

8 2
PCPPCCCC

DA

9 1
PPCPPCPPC

NE

提示

数据范围

对于全部数据，$1\le k<n\le 350$，红色石头至少出现 $2k-1$ 次。

说明

本题总分 $70$ 分。

本题译自 Croatian Open Competition in Informatics 2021/2022 Contest #1 T2 Kamenčići。