Problem Description

Given an $N \times N$ letter matrix and an integer $K$. Is there a consecutive sequence of $K$ columns such that after rearranging the letters within each row (i.e., only swapping letters within the same row), the original matrix has two identical rows?

Input Format

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain $N$ characters, representing the original letter matrix.

Output Format

If there is a solution that meets the criteria, output DA; otherwise, output NE.

Sample Input and Output

Sample Input #1

4 2
abcd
acbd
enaa
moze

Sample Output #1

DA

Sample Input #2

2 2
aa
aa

Sample Output #2

DA

Sample Input #3

3 2
nec
uuc
iti

Sample Output #3

NE

Notes

Sample 1 Explanation

Selecting the 2nd and 3rd columns and swapping the letters in these columns for the 2nd, 3rd, and 4th rows results in the new matrix:

abcd
abcd
eana
mzoe

Here, the 1st and 2nd rows are identical, thus satisfying the condition.

Data Size and Constraints

For 30% of the data, $N \le 10$.

For another 40% of the data, $N \le 200$.

For 100% of the data, $2 \le K \le N \le 500$.

Note

This problem's score is set according to the original COCI contest, with a maximum score of $90$.

The problem is translated from COCI2018-2019 CONTEST #5 T3 Ispit.

见题面 Input 部分

见题面 Output 部分