25552번 - 잔디 예측하기

잔디 예측사는 미래에 아주 유망한 직업이다. 잔디 예측사 1급 시험을 통과하기 위해서는 현재 잔디의 위치를 보고 미래에 잔디가 어떻게 퍼지는지 계산할 수 있어야 한다.

잔디 예측 분야의 개념서인 잔디의 정석에 의하면, 직사각형 모양 토지를 단위 정사각형 크기의 격자 칸들로 나눠 각각의 칸을 잔디가 있는 칸과 잔디가 없는 칸으로 분류하며, 잔디가 있는 칸에서 잔디가 없는 가까운 칸으로 퍼져나가는 규칙을 찾는다. 잔디의 정석에 쓰여진 규칙은 다음과 같다.

1. 잔디가 있는 모든 칸에서 단위 시간마다 가까운 칸으로 잔디가 퍼질 수 있다.
2. 한 칸에서 가까운 칸이란, 그 칸에서 상하좌우로 $D$번 이하로 움직여 도달할 수 있는 칸들을 말한다.
3. 잔디가 퍼지는 칸의 수는 무작위하다. 잔디가 퍼지지 않을 수도 있고 가까운 모든 칸에 잔디가 퍼질 수도 있다. 잔디가 퍼질 때 원래 잔디가 있던 칸은 유지되며, 원래 잔디가 있던 칸에 잔디가 퍼지면 아무 일도 일어나지 않는다.

현재 잔디의 상태와 예측한 미래의 잔디의 상태가 주어질 때, 현재 잔디가 위의 규칙을 따라 퍼진다면 충분한 시간이 지난 후 예측한 잔디의 상태와 같아질 수 있는지 판단해 보자.

첫째 줄에 직사각형 모양 토지의 행과 열의 수 $N, M$이 주어진다. $(1 \leq N, M \leq 1\,000)$

이후 초기 잔디의 상태가 $N$줄에 걸쳐 각각 $M$칸씩 주어진다.

이후 잔디가 퍼질 범위 $D$가 주어진다. $(1 \leq D \leq 8)$

이후 예측한 잔디의 상태가 $N$줄에 걸쳐 각각 $M$칸씩 주어진다.

O는 잔디가 있는 칸을, X는 잔디가 없는 칸을 나타낸다.

현재 잔디가 위의 규칙을 따라 퍼질 때 충분한 시간이 지난 후 예측한 잔디의 상태와 같아질 수 있다면 YES, 아니라면 NO를 출력하여라.