题目背景

原时限 5s，这里设为 1s，经测试正确算法可以正常通过。

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

题目描述

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

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

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

输入格式

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

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

输出格式

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

2 0
ox
ox

DA

3 1
ooo
xoo
oox

NE

4 2
oxxo
xxox
oxoo
oxxo

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$。

说明

本题分值按 COCI 原题设置，满分 $90$。这里只选取其中具有梯度的 $18$ 个测试点进行评测。

题目译自 COCI2018-2019 CONTEST #3 T3 Sajam。