Patkice II

Holywood가 두 섬 사이에서 성공한 우산 항해의 이야기를 영화로 만든 뒤, Netflix 경영진은 세 마리 오리의 여정을 시리즈물로 만들기로 했다.

COCI 20/21 1라운드에서 기억하겠지만, 오리들은 바다 해류 지도를 가지고 있다. 오리들은 함께 여행한다. 오리들이 사는 섬은 문자 o로 표시된다. 오리들은 네 방향 중 어느 방향으로든 항해를 시작할 수 있다. 이 바다의 해류는 네 방향 중 하나로 흐르며, 동에서 서로 가는 >, 서에서 동으로 가는 <, 북에서 남으로 가는 v, 남에서 북으로 가는 ^로 표시된다. 오리들이 해류가 있는 칸에 있으면 그 해류 방향으로 한 칸 이동한다.

잔잔한 바다는 .으로 표시된다. 해류가 오리들을 잔잔한 바다 칸, 지도 밖, 또는 출발 섬으로 데려가면 항해가 끝난다. 오리들이 방문하려는 섬은 x로 표시된다.

넷플릭스는 시리즈를 더 흥미롭게 만들려고 이야기를 바꿨다. 바다에는 이제 오리가 사이클에 갇힐 수 있는 야생 소용돌이와, 오리를 지도 밖으로 실어 나르는 해류가 있다. (오리들 사이에 삼각관계도 생기지만, 지금은 중요하지 않다.)

그래서 원래 해류 지도가 바뀌었다. 마감에 쫓긴 감독이 실수를 몇 개 했고, 이제 해류를 따라서는 오리들이 출발 섬에서 목표 섬까지 갈 수 없다.

넷플릭스 감독은 매우 중요한 사람들이라 줄거리의 허점을 따지는 데 시간을 쓰지 않는다. 따라서 여러분의 일은 오리들이 출발 섬에서 목표 섬까지 갈 수 있도록 지도의 문자를 가능한 한 적게 바꾸는 것이다.

이야기 전개를 위해 o와 x 칸은 수정할 수 없다. 나머지 칸은 해류 또는 잔잔한 바다이며(<>v^. 중 하나), 이 칸들의 문자는 같은 집합 <>v^. 안의 다른 문자로 바꿀 수 있다.

첫 줄에는 지도의 행 수 $r$과 열 수 $s$가 정수로 주어진다 ($3 \le r, s \le 2000$).

이어지는 $r$개 줄에는 문자 집합 o<>v^.x에서 고른 문자가 각각 $s$개씩 주어진다. 지도에는 문자 o가 정확히 하나, 문자 x가 정확히 하나 있으며, 두 문자는 인접하지 않다.

첫 줄에 $k$를 출력한다. $k$는 오리들이 출발 섬에서 목표 섬까지 갈 수 있도록 하는 최소 변경 수이다.

이어지는 $r$개 줄에는 입력 지도와 정확히 $k$개 칸에서만 다르고 위 조건을 만족하는 지도를 각 줄 $s$문자로 출력한다. 조건을 만족하는 지도가 여러 개이면 그중 아무거나 출력한다.