P7376 [COCI 2018/2019 #5] Ispit

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?

The first line contains integers $N, K$. The next $N$ lines each contain $N$ characters, representing the original letter matrix.

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

#### Sample 1 Explanation Choose columns $2, 3$, and swap the letters in these two columns within rows $2, 3, 4$, obtaining the new matrix: ```plain 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](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #5](https://hsin.hr/coci/archive/2018_2019/contest5_tasks.pdf) _T3 Ispit_.** Translated by ChatGPT 5