#include <iostream>

#include <string>

#include <queue>

#include <cstring>

using namespace std;

const int N=;

const int inf=;

int n,m;

string mp[];

int vis[][];

struct p

{

    int x,y;

};

p in[],ou[];

int d[][];

struct node

{

    int s;

    p po;

};

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

bool ok(p px)

{

    if(px.x<||px.y<)return ;

    if(px.x>=n||px.y>=n)return ;

    if(vis[px.y][px.x]) return ;

    if(mp[px.y][px.x]=='#')return ;

    return ;

}

void bfs(int np)

{

    queue<node> q;

    node ii;

    ii.s=;

    ii.po=ou[np];

    q.push(ii);

    memset(vis,,sizeof vis);

    vis[ii.po.y][ii.po.x]=;

    d[np][np]=;

    while(!q.empty())

    {

        node now=q.front();

        q.pop();

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

        {

            if(i==np)continue;

            if(now.po.x==in[i].x&&now.po.y==in[i].y)

                d[np][i]=now.s;

        }

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

        {

            node nx=now;

            nx.s++;

            nx.po.x+=dir[i][];

            nx.po.y+=dir[i][];

            if(ok(nx.po))

            {

                vis[nx.po.y][nx.po.x]=;

                q.push(nx);

            }

        }

    }

}

int dp[][];

int numid[];

struct dpx

{

    int d;

    int po;

    dpx(int dd,int pp)

    {

        d=dd;

        po=pp;

    }

};

int main()

{

    cin.sync_with_stdio(false);

    while(cin>>n>>m)

    {

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

            cin>>mp[i];

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

        {

            cin>>in[i].y>>in[i].x>>ou[i].y>>ou[i].x;

            in[i].x--;

            in[i].y--;

            ou[i].x--;

            ou[i].y--;

        }

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

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

                d[i][j]=inf;

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

            bfs(i);

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

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

                dp[i][j]=inf;

        int dx=;

        queue<dpx> q;

        int ad=;

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

        {

            ad+=dx;

            dp[dx][i]=;

            numid[i]=dx;

            q.push(dpx(dx,i));

            dx<<=;

        }

        while(!q.empty())

        {

            dpx now=q.front();

            q.pop();

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

            {

                if((now.d&numid[i])==)

                {

                    dpx nx=now;

                    nx.d+=numid[i];

                    nx.po=i;

                    if(dp[nx.d][nx.po]>dp[now.d][now.po]+d[now.po][nx.po])

                    {

                        dp[nx.d][nx.po]=dp[now.d][now.po]+d[now.po][nx.po];

                        q.push(nx);

                    }

                }

            }

        }

        int ans=inf;

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

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

        if(ans>=inf)cout<<-<<endl;

        else

            cout<<ans<<endl;

    }

    return ;

}