Sajam

Στο πνεύμα των Χριστουγέννων ο Milo οργάνωσε τη δική του χριστουγεννιάτικη έκθεση. Θα είναι η καλύτερη στην Ευρώπη! Το βράδυ τελειώνει και ήρθε η στιγμή να σβήσουμε τα φώτα. Μερικοί ήταν τόσο αυθάδεις, που δεν θέλησαν καν να σβήσουν τα φώτα στις κερκίδες τους! Δεδομένου ότι το ρεύμα είναι όλο και πιο ακριβό, ο Milo θέλει να σβήσουν γρήγορα όλα τα φώτα. Για αυτό θα χρησιμοποιήσει το legendary-electric-electronic-tablet (LEET), αλλά χρειάζεται τη βοήθειά σας.

Η χριστουγεννιάτικη έκθεση του Milo αποτελείται από πάγκους, που είναι διατεταγμένοι σε ~N~ σειρές, από τις οποίες η καθεμία αποτελείται από ~N~ περίπτερα. Στο LEET του ο Milo έχει 2 κουμπιά:

• Πατώντας το πρώτο κουμπί, ο Milo φαντάζεται μία σειρά, την ~x~.
  Στη συνέχεια, το LEET ανάβει κάθε βάση της ~x~-οστής σειράς που είχε απενεργοποιηθεί, αλλά σβήνει, επίσης, κάθε βάση της ~x~-οστής σειράς που είχε ενεργοποιηθεί.
• Πατώντας το δεύτερο κουμπί, ο Milo φαντάζεται μια στήλη, την ~x~.
  Στη συνέχεια, το LEET ανάβει κάθε βάση της ~x~-οστής στήλης που είχε απενεργοποιηθεί, αλλά σβήνει, επίσης, κάθε βάση της ~x~-οστής στήλης που είχε ενεργοποιηθεί.

Πατώντας τον αφαλό του (το "τρίτο κουμπί"), ο Milo θα περπατήσει σε μια συγκεκριμένη βάση και θα την ενεργοποιήσει (ή θα την απενεργοποιήσει). Το πρόβλημα είναι ότι έχει τραυματίσει το πόδι του, οπότε για να μην πάθει πνευμονική εμβολή, ο γιατρός έχει συνταγογραφήσει ότι το «τρίτο κουμπί» πρέπει να πατηθεί το πολύ ~K~ φορές ~(K \le N)~. Ευτυχώς το πρώτο και το δεύτερο κουμπί μπορεί να το πατήσει όσες φορές θέλει.

Είναι δυνατόν ο Milo να κλείσει όλες τις κερκίδες με αυθαίρετη αλληλουχία ενεργειών;

Είσοδος

Στην πρώτη γραμμή εισόδου υπάρχουν δύο ακέραιοι αριθμοί, οι ~N~ και ~K\;(1 \le N \le 1\,000, 0 \le K \le N)~.
Στις επόμενες ~N~ γραμμές υπάρχουν ~N~ χαρακτήρες ~'x'~ ή ~'o'~, που είναι η αρχική κατάσταση των περιπτέρων της χριστουγεννιάτικης έκθεσης.
Το σύμβολο ~'x'~ αντιπροσωπεύει μια βάση που είναι απενεργοποιημένη και το σύμβολο ~'o'~ μια βάση που είναι ενεργοποιημένη.

Έξοδος

Εκτυπώστε την απάντηση στην ερώτηση που τέθηκε στο πρόβλημα: "DA" (το "ΝΑΙ" στα Κροατικά), εάν είναι δυνατόν ή "NE" (το "ΌΧΙ" στα Κροατικά) αν δεν είναι δυνατόν (χωρίς τα εισαγωγικά).

Βαθμολογία

Σε παραδείγματα αξίας τουλάχιστον 15 πόντων θα ισχύει ~K = 0~.
Σε παραδείγματα αξίας τουλάχιστον 15 πόντων το ~N~ θα είναι μικρότερο ή ίσο με 100.
Στα πρόσθετα παραδείγματα αξίας τουλάχιστον 30 πόντων, το ~N~ θα είναι αυστηρά μικρότερο από ~\frac{1}{2}N~.

Παραδείγματα

input

2 0
ox
ox

output

DA

input

3 1
ooo
xoo
oox

output

NE

input

4 2
oxxo
xxox
oxoo
oxxo

output

DA

Επεξήγηση του 3ου παραδείγματος:

Δίνεται μια πιθανή ακολουθία πατημάτων κουμπιών μετά τα οποία απενεργοποιούνται όλες οι βάσεις:

• Δεύτερο κουμπί (φανταστείτε τη στήλη 1).
• Τρίτο κουμπί (ενεργοποίηση πεδίου (2, 2)).
• Πρώτο κουμπί (φανταστείτε τη σειρά 2).
• Δεύτερο κουμπί (φανταστείτε τη στήλη 4).
• Τρίτο κουμπί (απενεργοποίηση πεδίου (3, 3)).