블루홀 다이빙 챌린지

신비의 바다를 중심으로 펼쳐지는 특별한 다이빙 대회가 열린다. 이번 대회에서 다이버는 한 번에 여러 물고기를 잡을 수 있는 특수한 작살을 장착하고 출전한다.

바다는 $N \times N$ 격자로 나타내고, 격자의 어떤 칸들에는 물고기가 존재한다. 작살의 유효 사거리는 $K$로, 다이버가 특정 칸에서 작살을 사용하면 그 칸의 상하좌우 $4$방향으로 사이에 정확히 $K$개의 칸을 두고 떨어진 곳에 존재하는 칸의 물고기를 한 번에 잡을 수 있다. 즉, 한 번의 작살질로 최대 $4$마리의 물고기를 잡을 수 있다. 또한 각 물고기는 최대 한 번만 잡힐 수 있다.

편의상 $i$번째 행 $j$번째 열의 격자칸을 $(i, j)$라고 나타내자. 예를 들어, $N = 5$, $K = 1$일 때, $(3, 3)$에서 작살을 사용하면 $(1, 3)$, $(3, 1)$, $(3, 5)$, $(5, 3)$의 물고기를 한 번에 잡을 수 있다.

$N \times N$ 격자에 존재하는 물고기 정보와 작살의 유효 사거리 $K$가 주어질 때, 최대한 많은 물고기를 잡기 위해 작살을 사용할 최소 개수의 칸을 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 격자의 크기를 나타내는 정수 $N$과 작살의 사거리를 나타내는 정수 $K$가 주어진다. ($3 \le N \le 25;$ $1 \le K \le N - 2$)

그다음 $N$ 개의 줄의 $i$ 번째 줄에는 격자의 $i$ 번째 행을 이루는 $N$ 개 문자가 공백 없이 주어진다. 각 문자는 ., O, x, @ 중 하나고, .는 물고기가 없음을, O는 물고기가 있음을 나타낸다. 또한 x는 작살을 던질 수 없는 곳임을, @는 작살을 던질 수 없지만 물고기가 있음을 나타낸다.

출력 형식

최대로 많은 물고기를 잡기 위해서 작살을 사용할 최소 개수의 칸을 나타내기 위해, 첫 줄부터 $N$개의 줄에 걸쳐, 각 줄마다 $N$개 문자를 공백 없이 출력한다. 각 문자는 . 또는 v이어야 하며, 문자 v는 작살을 사용할 칸을 나타낸다.

답이 여러 개일 경우, 아무거나 하나를 출력한다.

예제 1

3 1
O.O
.@.
O.x

v..
...
v..

예제 2

5 2
..O..
@x..O
..O..
.Ox..
...O.

.v...
...v.
.....
.....
....v

예제 설명

첫 번째 예제의 경우, $2$번의 작살질로 총 $3$마리의 물고기를 잡을 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설