#include <cstdio>

 #include <queue>

 #include <cstring>

 #include <algorithm>

 #define maxn 1000

 using namespace std;

 const int inf=<<;

 int n,m;

 char g[][];

 int gg[][];

 struct node

 {

     int x1,y1,x2,y2;

 } p[maxn],st3;

 int dis[][];

 int dir[][]= {{,},{,-},{,},{-,}};

 int dp[<<][];

 bool vis[maxn][maxn];

 int bfs(int s,int t)

 {

     queue<node>q;

     memset(vis,false,sizeof(vis));

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

     {

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

         {

             dis[i][j]=inf;

         }

     }

     node st;

     st.x1=p[s].x2;

     st.y1=p[s].y2;

     dis[p[s].x2][p[s].y2]=;

     vis[p[s].x2][p[s].y2]=true;

     q.push(st);

     while(!q.empty())

     {

         node st1=q.front();

         q.pop();

         if(st1.x1==p[t].x1&&st1.y1==p[t].y1)

         {

             return dis[p[t].x1][p[t].y1];

         }

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

         {

             int xx=st1.x1+dir[i][];

             int yy=st1.y1+dir[i][];

             if(xx>=&&xx<n&&yy>=&&yy<n&&g[xx][yy]!='#')

             {

                 if(!vis[xx][yy])

                 {

                     dis[xx][yy]=dis[st1.x1][st1.y1]+;

                     st3.x1=xx;

                     st3.y1=yy;

                     vis[xx][yy]=true;

                     q.push(st3);

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         memset(g,,sizeof(g));

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

         {

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

         }

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

         {

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

             p[i].x1-=;

             p[i].y1-=;

             p[i].x2-=;

             p[i].y2-=;

         }

         memset(dp,-,sizeof(dp));

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

         {

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

             {

                 if(i==j) gg[i][j]=;

                 else

                 gg[i][j]=bfs(i,j);

             }

         }

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

         {

             dp[<<i][i]=;

         }

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

         {

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

             {

                 if((i&(<<j))==) continue;

                 if(dp[i][j]==-)  continue;

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

                 {

                     if(gg[j][k]==-) continue;

                     if(i&(<<k)) continue;

                     if(dp[i|(<<k)][k]==-) dp[i|(<<k)][k]=dp[i][j]+gg[j][k];

                     else dp[i|(<<k)][k]=min(dp[i|(<<k)][k],dp[i][j]+gg[j][k]);

                 }

             }

         }

         int ans=inf;

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

         {

             if(dp[(<<m)-][i]!=-)

             ans=min(ans,dp[(<<m)-][i]);

         }

         if(ans==inf) printf("-1\n");

         else

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

     }

     return ;

 }