题目描述

给定一个 $N$ 行 $N$ 列的字母矩阵和整数 $K$。是否有连续的 $K$ 列，使得这 $K$ 列中每一行在行内进行重组（即只能交换同行的字母）后，能够使原矩阵有两行完全相同？

输入格式

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

接下来的 $N$ 行，每行输入 $N$ 个字符，表示原来的字母矩阵。

输出格式

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

4 2
abcd
acbd
enaa
moze

DA

2 2
aa
aa

DA

3 2
nec
uuc
iti

NE

提示

样例 1 解释

选定第 $2,3$ 列，并将第 $2,3,4$ 行中的这两列的字母进行交换，得到新矩阵：

abcd
abcd
eana
mzoe

这时，第 $1,2$ 行完全相同，因此满足题意。

数据规模与约定

对于 $30\%$ 的数据，$N \le 10$。

对于另外 $40\%$ 的数据，$N \le 200$。

对于 $100\%$ 的数据，$2 \le K \le N \le 500$。

说明

本题分值按 COCI 原题设置，满分 $90$。

题目译自 COCI2018-2019 CONTEST #5 T3 Ispit。