시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 2 2 40.000%

문제

After 26 years of studying, little Mirko took his potentially last exam. He confidently took his seat, sharpened his pencil and waited calmly for the professor's permission to start writing – after all, that was his favorite subject, Data Structures and Algorithms. But, as in any good story, this one also has that but... Namely, when he got his exam, Mirko could not even comprehend what was written in it. He only saw a meaningless matrix of letters with N rows and N columns.

Since the professor forbid leaving the classroom during the exam, Mirko decided to spend 2 hours coming up with his own task. Mirko was wondering if it is possible to select K consecutive columns of the matrix so that, after arbitrarily shuffling letters in the K selected columns’ rows, there are two equal rows of the matrix. Shuffling is allowed only inside of the same row within selected columns and it is possible that a row remains unchanged after such operation.

Can you solve Mirko's task?

입력

In the first line of the input there are two integer numbers N and K (2 ≤ K ≤ N ≤ 500).

The following N rows contain N lowercase letters of the english alphabet describing the matrix of the letters Mirko saw in the exam.

출력

Print “DA” (Croatian for yes, without the quotation marks) if it is possible to select the K consecutive columns that meet the conditions of the task. Otherwise print “NE” (Croatian for no, also without quotation marks).

예제 입력 1

4 2
abcd
acbd
enaa
moze

예제 출력 1

DA

E.g. we can choose columns 2 and 3 and change the matrix so that it looks like this (we can choose not to change the first row and swap 2nd and 3rd letters in other rows):

abcd
abcd
eana
mzoe

It is clear that the first and the second row are the same, thus satisfying the task condition

예제 입력 2

2 2
aa
aa

예제 출력 2

DA

예제 입력 3

3 2
nec
uuc
iti

예제 출력 3

NE