Description

You are given an $N$ by $N$ matrix consisting of lowercase letters and an integer $K$. Is there a set of $K$ consecutive columns such that, within these $K$ columns, for every row you may rearrange the letters inside that row (that is, you can only swap letters within the same row), and after doing so, the original matrix can have two rows that are exactly identical?

Input Format

The first line contains integers $N, K$.

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

Output Format

If there is a solution that satisfies the requirement, output DA; otherwise output NE.

4 2
abcd
acbd
enaa
moze

DA

2 2
aa
aa

DA

3 2
nec
uuc
iti

NE

Hint

Sample 1 Explanation

Choose columns $2, 3$, and swap the letters in these two columns within rows $2, 3, 4$, obtaining the new matrix:

abcd
abcd
eana
mzoe

Now rows $1$ and $2$ are exactly the same, so the requirement is satisfied.

Constraints

For all testdata, the input matrix is guaranteed to consist of lowercase letters.

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

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

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

Notes

The score for this problem follows the original COCI setting, with a full score of $90$.

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

Translated by ChatGPT 5