#include<cstdio>
#include<queue>
using namespace std;
int N,M;
//dep表示最短路径的长度,而total表示最短路径的条数
int dep,total;
char map[20][20],source,dest;
//表示被最短路径经过多少次,p用来纪录路径
int num[20][20],p_x[80],p_y[80];
int load,sx,sy,dx,dy;
//load factor
double lf[20][20];
//用bfs求最短路径长度
void short_path();
int main()
{
int i,j;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w+",stdout);
scanf("%d%d",&M,&N);
for(i=0;i<N;i++)
scanf("%s",map[i]);
for(i=0;i<M;i++)
for(j=0;j<N;j++)
lf[i][j]=0.0;
while(1)
{
getchar();
if(scanf("%c%c %d",&source,&dest,&load)==EOF || source=='X' || dest=='X')
break;
//printf("%c %c %d\n",source,dest,load);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
{
if(map[i][j]==source)
{
sx=i;
sy=j;
}
if(map[i][j]==dest)
{
dx=i;
dy=j;
}
}
//printf("sx=%d,sy=%d,dx=%d,dy=%d\n",sx,sy,dx,dy);
short_path();
/*
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
printf("%d\t",num[i][j]);
printf("\n");
}
*/
//dfs搜寻所有最短路径
for(i=0;i<M;i++)
for(j=0;j<N;j++)
if(map[i][j]=='.')
lf[i][j]+=num[i][j]*load*1.0/total;
}
for(i=0;i<M;i++)
{
printf("%6.2lf",lf[i][0]);
for(j=1;j<M;j++)
printf(" %6.2f",lf[i][j]);
printf("\n");
}
return 0;
}
void short_path()
{
//准备用bfs来求最短路径长度
queue<int> qx,qy;
int d[20][20],tnum[20][20],i,j,tx,ty,td,t;
bool mark[20][20];
for(i=0;i<N;i++)
for(j=0;j<M;j++)
d[i][j]=-1;
qx.push(sx) , qy.push(sy) , d[sx][sy]=0;
while(1)
{
tx=qx.front() , ty=qy.front() , td=d[tx][ty];
if(d[dx][dy]!=-1 && td>=d[dx][dy])
break;
if(tx-1>=0 && (map[tx-1][ty]=='.' || map[tx-1][ty]==dest) )
{
if(d[tx-1][ty]==-1)
qx.push(tx-1) , qy.push(ty) , d[tx-1][ty]=td+1;
}
if(tx+1 <N && (map[tx+1][ty]=='.' || map[tx+1][ty]==dest))
{
if(d[tx+1][ty]==-1)
qx.push(tx+1) , qy.push(ty) , d[tx+1][ty]=td+1;
}
if(ty-1>=0 && (map[tx][ty-1]=='.' || map[tx][ty-1]==dest))
{
if(d[tx][ty-1]==-1)
qx.push(tx) , qy.push(ty-1) , d[tx][ty-1]=td+1;
}
if(ty+1 <M && (map[tx][ty+1]=='.' || map[tx][ty+1]==dest))
{
if(d[tx][ty+1]==-1)
qx.push(tx) , qy.push(ty+1) , d[tx][ty+1]=td+1;
}
qx.pop() , qy.pop();
}
dep=d[dx][dy];
// printf("dep=%d\n",dep);
//逆推求所有路径数
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
tnum[i][j]=0;
mark[i][j]=false;
}
while(!qx.empty())
{
qx.pop();
qy.pop();
}
qx.push(dx) , qy.push(dy) ,tnum[dx][dy]=1 , mark[dx][dy]=true;
for(i=dep;i>0;i--)
{
while(1)
{
tx=qx.front() , ty=qy.front();
// printf("tx=%d ty=%d\n",tx,ty);
if(d[tx][ty]!=i)
break;
// printf("i=%d\n",i);
if(tx-1>=0 && d[tx-1][ty]+1==d[tx][ty])
{
tnum[tx-1][ty]+=tnum[tx][ty];
if(!mark[tx-1][ty])
qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true;
}
if(tx+1 <N && d[tx+1][ty]+1==d[tx][ty])
{
tnum[tx+1][ty]+=tnum[tx][ty];
if(!mark[tx+1][ty])
qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true;
}
if(ty-1>=0 && d[tx][ty-1]+1==d[tx][ty])
{
tnum[tx][ty-1]+=tnum[tx][ty];
if(!mark[tx][ty-1])
qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true;
}
if(ty+1 <M && d[tx][ty+1]+1==d[tx][ty])
{
tnum[tx][ty+1]+=tnum[tx][ty];
if(!mark[tx][ty+1])
qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true;
}
qx.pop() , qy.pop();
}
}
/*
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
printf("=%d\t",tnum[i][j]);
printf("\n");
}
*/
total=tnum[sx][sy];
// printf("total=%d\n",total);
//正推求每点的经过的最短路径数
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
num[i][j]=0;
mark[i][j]=false;
}
num[sx][sy]=total;
while(!qx.empty())
{
qx.pop();
qy.pop();
}
//qx.pop() , qy.pop();
qx.push(sx) , qy.push(sy) , mark[sx][sy]=true;
// printf("haha\n");
for(i=0;i<dep;i++)
{
while(1)
{
tx=qx.front() , ty=qy.front();
if(d[tx][ty]!=i)
break;
// printf("tx=%d ty=%d d=%d num=%d\n",tx,ty,d[tx][ty],num[tx][ty]);
t=0;
//把周围4个点的儿子为tx ty的点按比例分配
if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty])
{
t+=tnum[tx-1][ty];
if(!mark[tx-1][ty])
qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true;
}
if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty])
{
t+=tnum[tx+1][ty];
if(!mark[tx+1][ty])
qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true;
}
if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty])
{
t+=tnum[tx][ty-1];
if(!mark[tx][ty-1])
qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true;
}
if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty])
{
t+=tnum[tx][ty+1];
if(!mark[tx][ty+1])
qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true;
}
//
if(t)
{
if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty])
num[tx-1][ty]+=tnum[tx-1][ty]*num[tx][ty]/t;
if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty])
num[tx+1][ty]+=tnum[tx+1][ty]*num[tx][ty]/t;
if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty])
num[tx][ty-1]+=tnum[tx][ty-1]*num[tx][ty]/t;
if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty])
num[tx][ty+1]+=tnum[tx][ty+1]*num[tx][ty]/t;
}
//
qx.pop() , qy.pop();
}
}
}
