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 ~x^{th}~ row that had been turned off, but also turns off every stand of the ~x^{th}~ row that had been turned on.

• By pressing the second button, Milo imagines one column, ~x~.

  LEET then lights every stand of the ~x^{th}~ column that had been turned off, but also turns off every stand of the ~x^{th}~ 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 \le 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 an arbitrary sequence of actions?

Input

In the first line of input there are two integer numbers ~N~ and ~K~ from the task description ~(1 \le N \le 1\,000, 0 \le K \le 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.

Output

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

Scoring

In the test samples worth at least 15 points it will hold ~K = 0~.

In the additional test samples worth at least 15 points ~N~ will be less or equal to ~100~.

In the additional test samples worth at least 30 points ~K~ will strictly be less than ~\frac N 2~.

Sample Input 1

2 0
ox
ox

Sample Output 1

DA

Sample Input 2

3 1
ooo
xoo
oox

Sample Output 2

NE

Sample Input 3

4 2
oxxo
xxox
oxoo
oxxo

Sample Output 3

DA

Explanation for Sample Output 3

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)~).