#include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int ne[][]={{,},{,},{,-},{-,}};

 struct Node{

     int x,y,t;

     Node(){}

     Node(int x,int y,int t):x(x),y(y),t(t){}

 };

 int n,m,sn,ans,dis[][][][],vis[][];

 int x1[],y1[],x2[],y2[],dp[<<][],cf2[]={};

 char s[][];

 void bfs(int x,int y)

 {

     memset(vis,,sizeof(vis));

     vis[x][y]=;

     queue<Node> q;

     q.push(Node(x,y,));

     while(!q.empty())

     {

         Node p=q.front();

         q.pop();

         dis[x][y][p.x][p.y]=p.t;

         for(int i=;i<;i++)

         {

             int dx=p.x+ne[i][];

             int dy=p.y+ne[i][];

             if(dx<=||dx>n||dy<=||dy>n)

                 continue;

             if(!vis[dx][dy]&&s[dx][dy]!='#')

             {

                 vis[dx][dy]=;

                 q.push(Node(dx,dy,p.t+));

             }

         }

     }

 }

 int main()

 {

     for(int i=;i<=;i++)

         cf2[i]=cf2[i-]<<;

     while(~scanf("%d%d",&n,&m))

     {

         memset(dp,inf,sizeof(dp));

         memset(dis,inf,sizeof(dis));

         for(int i=;i<=n;i++)

             scanf("%s",s[i]+);

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 bfs(i,j);//预处理出距离

         for(int i=;i<m;i++)

             scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);

         for(int i=;i<m;i++)

             dp[<<i][i]=;//第一个走的管道不需要花费时间

         int maxm=(<<m)-;

         for(int i=;i<maxm;i++)

         {

             for(int j=;j<m;j++)

             {

                 if(i&cf2[j])//枚举已经走了的

                 {

                     for(int k=;k<m;k++)

                         if(!(i&cf2[k]))//枚举还没走的

                             dp[i+cf2[k]][k]=min(dp[i+cf2[k]][k],dp[i][j]+dis[x2[j]][y2[j]][x1[k]][y1[k]]);

                 }

             }

         }

         int ans=inf;

         for(int i=;i<m;i++)

             ans=min(ans,dp[maxm][i]);

         if(ans>=inf)

             printf("%d\n",-);

         else

             printf("%d\n",ans);

     }

     return ;

 }