经过 26 年的学习，小 Mirko 迎来了他可能是最后一次的期末考试。他自信地坐下，削好铅笔，平静地等待教授允许开始答题——毕竟，这是他最喜欢的科目《数据结构与算法》。但是，就像所有好故事一样，这里也有一个“但是”……也就是说，当他拿到试卷时，Mirko 甚至无法理解上面写了什么。他只看到一个由字母组成的无意义的 $N$ 行 $N$ 列的矩阵。

由于教授禁止在考试期间离开教室，Mirko 决定花 2 个小时来自己出一道题。Mirko 想知道，是否可以选择矩阵中连续的 $K$ 列，使得在对这 $K$ 个选中列中每一行内的字母进行任意重排后，矩阵中存在两个完全相同的行。重排仅允许在选中列的同一行内部进行，且在操作后，某些行可以保持不变。

你能解决 Mirko 的问题吗？

输入格式

输入的第一行包含两个整数 $N$ 和 $K$（$2 \le K \le N \le 500$）。

接下来的 $N$ 行，每行包含 $N$ 个英文小写字母，描述 Mirko 在考试中看到的字母矩阵。

输出格式

如果可以选择满足任务条件的连续 $K$ 列，则输出 DA（克罗地亚语中的“是”，不带引号）。否则，输出 NE（克罗地亚语中的“否”，同样不带引号）。

子任务

在占总分 30% 的测试数据中，满足 $N \le 10$。

在占总分额外 40% 的测试数据中，满足 $N \le 200$。

样例

输入样例 1

4 2
abcd
acbd
enaa
moze

输出样例 1

DA

输入样例 2

2 2
aa
aa

输出样例 2

DA

输入样例 3

3 2
nec
uuc
iti

输出样例 3

NE

说明

第一个样例的解释：

例如，我们可以选择第 2 列和第 3 列，并对矩阵进行调整，使其看起来像这样（我们可以选择不改变第一行，并交换其他行中的第 2 个和第 3 个字母）：

abcd
abcd
eana
mzoe

显然，第一行和第二行是相同的，从而满足了任务的条件。