아, 쑤시는 발

요즘 인도가 붐비면서 차도로 밀려나 다친 사람이 여럿 나왔다. 시청은 인도마다 하루에 보행자가 얼마나 지나가는지 알고 싶어 하고, 그 결과를 보고 인도를 더 놓는 데 예산을 쓸지 정한다. 조사원이 몇 개 블록의 건물을 돌면서 건물마다 발생하는 보행자 통행량을 기록했다. 이 조사 자료를 인도 이용량 수치로 바꾸는 것이 여러분이 할 일이다.

프로그램은 지도의 크기와 지도를 읽는다. 지도에는 건물, 도로, 건물 출입구가 표시되어 있다. 이어서 출입구 쌍 사이의 보행자 통행량 목록을 읽는다. 각 출발지와 목적지 사이에서 보행자가 어떤 경로로 다니는지 구하고, 도로 칸마다 실리는 통행량을 모두 더해서 칸별 총 통행량을 출력한다.

테스트 케이스의 첫 줄에는 지도의 열 수 $X$와 행 수 $Y$가 주어진다. 둘 다 20보다 작은 양의 정수다.

다음 $Y$개 줄에는 지도를 나타내는 문자가 정확히 $X$개씩 있다. x와 X는 출입구가 아닌 건물 칸, .는 도로 칸, A부터 O까지의 알파벳은 출입구를 뜻한다. 알파벳 하나는 지도에 많아야 한 번 나온다.

지도 다음에는 보행자 경로가 한 줄에 하나씩 주어진다. 한 줄에는 출발지 알파벳과 목적지 알파벳이 공백 없이 붙어 있고, 그 뒤에 공백을 두고 보행자 통행량이 음이 아닌 정수로 주어진다. 출발지와 목적지는 항상 다르다. 한 테스트 케이스의 경로는 25개 이하이고, 모든 경로는 지도 위에 유효한 길이 하나 이상 있다.

경로 목록은 XX 0 줄로 끝난다. 이 줄 뒤에 다음 테스트 케이스가 이어질 수 있다. 입력은 지도 크기 자리에 0 0이 오는 줄로 끝난다.

테스트 케이스마다 $Y$개 줄을 출력한다. 각 줄에는 값 $X$개를 공백 하나로 구분해서 쓴다. 값은 그 칸의 총 통행량이고, 소수점 아래 둘째 자리까지 너비 6칸에 오른쪽 정렬로 출력한다(C의 %6.2f 형식). 테스트 케이스 사이에는 빈 줄을 넣지 않고 이어서 출력한다.

입력 자료에서는 어떤 칸의 통행량도 100분의 1 두 눈금의 정확히 중간에 놓이지 않으므로, 반올림 방향이 답을 바꾸는 일은 없다.

• 지도는 칸으로 나뉜다. 각 칸은 도로 칸, 건물 칸, 출입구 칸 중 하나이고, 출입구 칸은 그 건물의 입구이자 출구다. 지도의 도로 칸은 90개를 넘지 않는다.
• 보행자는 도로 칸과 자기 경로의 출발지, 목적지 칸만 지나간다. 출입구 칸도 건물의 일부이므로 다른 건물의 출입구는 지나갈 수 없다.
• 사람은 언제나 출발지에서 목적지까지 최단 경로로 간다. 최단 경로의 길이는 75칸을 넘지 않는다.
• 길이가 같은 최단 경로가 여럿이면 통행량은 그 경로들에 똑같이 나뉜다. 한 경로의 최단 경로 가짓수는 50000가지 미만이다.
• 건물 모서리처럼 출입구가 도로와 맞닿은 면이 여럿이면, 보행자는 그중 어느 면으로든 드나들 수 있다.
• 이동은 북, 동, 남, 서로만 한다. 대각선 이동은 없다.
• 보행자는 건물을 지나가거나 지도 밖으로 나갈 수 없다.
• 도로 한 칸은 인도 하나로 본다. 실제로 도로마다 인도가 양쪽에 있다는 점은 무시한다.
• 출입구 칸 자체에는 통행량이 쌓이지 않는다.
• 출발지와 목적지가 지도에서 서로 붙어 있으면 보행자는 바로 건너갈 수 있다. 이때는 도로를 쓰지 않으므로 어느 칸에도 통행량이 생기지 않는다.