이상 이하의 정수를 채워넣을 수 있는 행 열 크기의 격자가 있다. 격자의 번째 행과 번째 열이 만나는 칸을 라고 한다. 격자의 어떤 칸은 정수를 채워넣을 수 없게 막혀 있고, 어떤 칸은 이미 정수가 채워져 있다.
격자의 두 칸이 한 변을 공유한다면 두 칸이 인접하다고 정의한다. 격자 위의 경로는 인접한 칸으로 이동하면서 방문하는 칸의 나열이고, 경로의 가중치는 격자 위의 경로에 채워진 수의 합이다. 에서 로 가는 최단 거리는 에서 출발하여 에 도착하는 경로의 가중치 중 가장 작은 값이다.
격자의 처음 상태와 , 가 주어질 때 격자의 채울 수 있는 칸을 모두 적절히 채워넣어 에서 로 가는 최단거리가 정확히 가 되게 하고 싶다. 에서 로 가는 최단거리가 정확히 가 되도록 격자를 채울 수 있는지 확인하고, 가능하다면 그 중 한 가지를 출력해보자.
첫째 줄에 격자의 크기를 나타내는 양의 정수 과 이 공백으로 구분되어 주어진다.
둘째 줄부터 번째 줄까지 격자의 처음 상태를 나타내는 문자열이 주어진다. 각 문자열은 이상 이하의 정수, , 만으로 이루어진 길이 인 문자열이다. 번째 줄의 j번째 문자는 의 상태를 의미한다. 이상 이하의 정수이면 해당하는 정수가 채워져 있다는 것을, 이면 채워넣을 수 있다는 것을, 이면 사용할 수 없음을 의미한다.
만약 최단 거리가 정확히 가 되도록 격자를 채울 수 있으면 개의 줄에 걸쳐 격자의 상태를 출력한다. 에 정수가 채워져 있으면 번째 줄 번째 문자로 그 정수를 출력한다. 가 사용할 수 없는 칸이면 번째 줄 번째 문자로 를 출력한다. 정수를 채울 수 있는 모든 칸에 정수를 채워야 하며, 이미 정수가 채워진 칸의 정수를 바꾸면 안 된다.
#..#번째 줄에는 시작점의 위치와 끝점의 위치를 나타내는 가 공백으로 구분되어 주어진다. 와 는 채워져 있지 않은 칸이다.
번째 줄에는 원하는 최단 거리를 나타내는 값 가 주어진다.
#만약 최단거리가 정확히 가 되도록 격자를 채울 수 없으면 대신 -1을 출력한다.