题目背景

Milo 组织了一场圣诞游园会。结束后，他想通过 LEET 来实现熄灯。

题目描述

每个区域都由 $N$ 行组成，其中每行有 $N$ 个摊位。现有 $3$ 种操作方式改变发光状态指将原来发光的灯改为熄灭，反之亦然）：

1. LEET 将选定一整行，并自动将这行所有的灯改变发光状态。
2. LEET 将选定一整列，并自动将这列所有的灯改变发光状态。
3. Milo 将选定一个摊位，并手动将该摊位的灯改变发光状态。

是否有方案使得 Milo 能在最多进行 $K$ 次操作 3 的情况下，将所有灯全部熄灭？

输入格式

第一行输入整数 $N,K$。

接下来的 $N$ 行，每行有 $N$ 个字符 x 或 o，表示圣诞游园会对应摊位灯的发光状态。其中 x 指熄灭，o 指发光。

输出格式

如果有符合题意的方案，则输出 DA，否则输出 NE。

样例 #1

样例输入 #1

2 0
ox
ox

样例输出 #1

DA

样例 #2

样例输入 #2

3 1
ooo
xoo
oox

样例输出 #2

NE

样例 #3

样例输入 #3

4 2
oxxo
xxox
oxoo
oxxo

样例输出 #3

DA

提示

样例 3 解释

一种符合题意的方案：

• 执行操作 $2$，选定第 $1$ 列。
• 执行操作 $3$，选定 $(2,2)$。
• 执行操作 $1$，选定第 $2$ 行。
• 执行操作 $2$，选定第 $4$ 列。
• 执行操作 $3$，选定 $(3,3)$。

数据规模与规定

对于 $15$ 分的数据，$K=0$。

对于另外 $15$ 分的数据，$N \le 100$。

对于另外 $30$ 分的数据，$K \lt \dfrac{N}{2}$。

对于 $100\%$ 的数据，$1 \le N \le 1000$，$0 \le K \le N$。