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

문제

In the spirit of advent Milo organized his own Christmas fair. It will be the best one in Europe! The evening ends and the moment has come to turn off the lights. Some were so insolent that they didn’t even deign to turn off lights on their stands! Since the electricity is more and more expensive, Milo wants all the lights to be turned off quickly. For this he will use the legendary-electric-electronic-tablet (LEET), but he also needs your help.

Milo's Christmas fair consists of stalls that are arranged in N rows of which every consists of N stands. On his LEET Milo has 2 buttons:

  • By pressing the first button, Milo imagines one row, x. LEET then lights every stand of the xth row that had been turned off, but also turns off every stand of the xth row that had been turned on.
  • By pressing the second button, Milo imagines one column, x. LEET then lights every stand of the xth column that had been turned off, but also turns off every stand of the xth column that had been turned on.

By pressing his own belly button (the “third button”), Milo will decide to walk to a particular stand and physically turn it on (or turn it off). The problem is that he has injured his leg so in order not to get a pulmonary embolism, the doctor has prescribed that the “third button” should be pressed at most K times (K ≤ N). Fortunately, the first and second button he can press as much as he wants.

Is it possible that Milo will shut down all the stands with arbitrary sequence of actions?

입력

In the first line of input there are two integer numbers N and K from the task description (1 ≤ N ≤ 1 000, 0 ≤ K ≤ N).

In the next N lines there are N characters 'x' or 'o', the initial state of the stands of the Christmas fair.

The symbol 'x' represents a stand that is turned off and 'o' a stand that is turned on.

출력

Print the answer to the question from the task: “DA” (Croatian for yes) if possible or “NE” (Croatian for no) if it is not (without the quotation marks).

예제 입력 1

2 0
ox
ox

예제 출력 1

DA

예제 입력 2

3 1
ooo
xoo
oox

예제 출력 2

NE

예제 입력 3

4 2
oxxo
xxox
oxoo
oxxo

예제 출력 3

DA

Explanation of the third test sample:

One possible sequence of button pressures is given after which all the stands are turned off:

  • Second button (imagine column 1).
  • Third button (turn on field (2, 2)).
  • First button (imagine row 2).
  • Second button (imagine column 4).
  • Third button (turn off field (3, 3)).