为了庆祝降临节，Milo 组织了他自己的圣诞集市。这将是欧洲最好的集市！夜幕降临，是时候关掉所有的灯了。有些摊主太粗心了，甚至没有主动关掉他们摊位上的灯！由于电费越来越贵，Milo 希望能快速关掉所有的灯。为此，他将使用传说中的“电子电力平板电脑”（LEET），但他同时也需要你的帮助。
Milo 的圣诞集市由排列成 $N$ 行的摊位组成，每行包含 $N$ 个摊位。在他的 LEET 上，Milo 有 2 个按钮：
- 按下第一个按钮，Milo 选定某一行 $x$。LEET 会将第 $x$ 行所有原本关闭的灯点亮，同时也将所有原本点亮的灯熄灭。
- 按下第二个按钮，Milo 选定某一列 $x$。LEET 会将第 $x$ 列所有原本关闭的灯点亮，同时也将所有原本点亮的灯熄灭。
通过按下他自己的肚脐眼（“第三个按钮”），Milo 可以走到某个特定的摊位前，手动打开或关闭它（即翻转其状态）。问题在于他的腿受了伤，为了避免引起肺栓塞，医生建议他最多只能按下“第三个按钮” $K$ 次（$K \le N$）。幸运的是，第一和第二个按钮他可以无限次按下。
是否可以通过任意的操作序列，将所有摊位的灯全部关闭？
输入格式
第一行包含两个整数 $N$ 和 $K$，含义如题面所述（$1 \le N \le 1\,000$，$0 \le K \le N$）。
接下来的 $N$ 行，每行包含 $N$ 个字符 'x' 或 'o'，表示圣诞集市摊位的初始状态。字符 'x' 表示灯是关闭的，'o' 表示灯是打开的。
输出格式
如果可以关闭所有灯，输出 DA（克罗地亚语中的“是”）；如果不能，输出 NE（克罗地亚语中的“否”）（均不包含引号）。
子任务
在价值至少 15 分的测试样例中，满足 $K = 0$。
在另外价值至少 15 分的测试样例中，满足 $N \le 100$。
在另外价值至少 30 分的测试样例中，满足 $K < \frac{1}{2} N$。
样例
输入样例 1
2 0 ox ox
输出样例 1
DA
输入样例 2
3 1 ooo xoo oox
输出样例 2
NE
输入样例 3
4 2 oxxo xxox oxoo oxxo
输出样例 3
DA
说明
第三个样例的解释：
一种可行操作序列如下，操作后所有灯都将被关闭：
- 按下第二个按钮（选定第 1 列）。
- 按下第三个按钮（手动翻转格子 $(2, 2)$ 的状态）。
- 按下第一个按钮（选定第 2 行）。
- 按下第二个按钮（选定第 4 列）。
- 按下第三个按钮（手动翻转格子 $(3, 3)$ 的状态）。