\(N\times N\) 크기의 체스판 위에 나이트 한 개와 여러 개의 아군 기물이 놓여 있다.

나이트는 현재 위치에서 가로로 두 칸, 세로로 한 칸 또는 가로로 한 칸, 세로로 두 칸 떨어진 위치로 이동할 수 있다. 따라서 한 번의 이동으로 갈 수 있는 위치는 최대 여덟 곳이다.

가운데의 나이트는 한 번의 이동으로 파란색으로 표시된 여덟 칸 중 하나에 도착할 수 있다.

나이트는 다른 기물을 뛰어넘을 수 있다. 따라서 이동하는 중간에 아군 기물이 있어도 상관없지만, 아군 기물이 놓인 칸에 착지할 수는 없다.

나이트의 시작 위치에서 최대 \(K\)번 이동하여 도착할 수 있는 모든 칸을 구하여라. 시작 위치는 \(0\)번 이동하여 도착할 수 있는 칸으로 취급한다.

입력

첫째 줄에 체스판의 크기 \(N\)과 최대 이동 횟수 \(K\)가 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에 체스판의 상태를 나타내는 길이 \(N\)의 문자열이 주어진다. 문자열의 문자는 다음 의미를 가진다.

• S: 나이트의 시작 위치
• .: 비어 있는 칸
• X: 아군 기물이 놓인 칸

S는 체스판에 정확히 하나 존재한다.

• \(1\le N\le 500\)
• \(0\le K\le 30\)

출력

\(N\)개의 줄에 걸쳐 도착 가능 여부를 나타내는 \(N\times N\) 격자를 출력한다.

입력 체스판의 각 칸에 대해 최대 \(K\)번 이동하여 도착할 수 있으면 1, 그렇지 않으면 0을 출력한다. 각 줄의 숫자 사이에는 공백을 출력하지 않는다.

아군 기물이 놓인 칸은 항상 0이며, 나이트의 시작 위치는 항상 1이다.

예제 입력 1

5 1
.X...
.....
..S..
....X
.....

예제 출력 1

00010
10001
00100
10000
01010

예제 설명 1

시작 위치는 \(0\)번 이동하여 도착할 수 있으므로 1로 표시한다.

나이트가 한 번 이동하여 도착할 수 있는 칸 가운데 첫 번째 행의 두 번째 칸과 네 번째 행의 다섯 번째 칸에는 아군 기물이 있으므로 도착할 수 없다. 나머지 여섯 칸에는 도착할 수 있다.

예제 입력 2

3 2
...
.S.
...

예제 출력 2

000
010
000

예제 설명 2

최대 \(2\)번 이동할 수 있지만, 시작 위치에서 한 번 이동하여 체스판 안에 도착할 수 있는 칸이 없다. 따라서 시작 위치만 1로 표시한다.