사잠 (Sajam)

Milo가 직접 크리스마스 장터를 열었다. 장터의 가판대는 $N$행에 걸쳐 놓여 있고, 각 행에는 $N$개의 가판대가 있다. 가판대마다 조명이 켜져 있거나 꺼져 있다. Milo는 모든 조명을 최대한 빨리 끄고 싶어 하며, 이를 위해 LEET(legendary-electric-electronic-tablet)라는 태블릿을 사용한다.

태블릿에는 버튼이 두 개 있다.

• 첫 번째 버튼은 행 번호 $x$를 고른다. 그 행의 가판대마다 켜진 것은 끄고, 꺼진 것은 켠다.
• 두 번째 버튼은 열 번호 $x$를 고른다. 그 열의 가판대에 같은 작업을 한다.

세 번째 버튼은 Milo가 배꼽 버튼을 누르는 것이다. 특정 가판대로 걸어가서 그 가판대의 조명을 켜거나 끈다. Milo는 다리를 다쳐서 세 번째 버튼은 최대 $K$번까지만 누를 수 있다. 첫 번째와 두 번째 버튼은 원하는 만큼 누를 수 있다.

버튼을 어떤 순서로 누르든, Milo가 모든 가판대의 조명을 끌 수 있는가?

첫째 줄에 정수 $N$과 $K$가 주어진다 ($1 \le N \le 1000$, $0 \le K \le N$). 다음 $N$개의 줄에는 각각 $N$개의 문자가 주어지며, 가판대의 초기 상태를 나타낸다. x는 꺼진 가판대, o는 켜진 가판대이다.

모든 가판대의 조명을 끌 수 있으면 DA, 없으면 NE를 출력한다.