#include<iostream>#include<cstdio>#include<queue>using namespace std;const int NO=56;const int INF=1000000000;struct X{    int x,y;    int key;}dir[]={{-1,0}/*&iexcl;ü*/,{0,1}/*&iexcl;ú*/,{1,0}/*&iexcl;&yacute;*/,{0,-1}/*&iexcl;&ucirc;*/},a,b;int n,m,q;int MAP[NO][NO][NO][NO];int key[NO][NO];int step[NO][NO][1024];void reset_step(){    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            for(int k=0;k<1<<q;k++)                step[i][j][k]=INF;}int bfs(){    reset_step();    queue<X> t;    a.x=a.y=1;    a.key=0;    step[a.x][a.y][a.key]=0;    t.push(a);    while(!t.empty())    {        a=t.front();        t.pop();        if(a.x==n&&a.y==m)            return step[a.x][a.y][a.key];        for(int i=0;i<4;i++)        {            b.x=a.x+dir[i].x;            b.y=a.y+dir[i].y;            if((MAP[a.x][a.y][b.x][b.y]&a.key)==MAP[a.x][a.y][b.x][b.y])            {                b.key=a.key|key[b.x][b.y];                if(step[b.x][b.y][b.key]==INF)                {                    step[b.x][b.y][b.key]=step[a.x][a.y][a.key]+1;                    t.push(b);                }            }        }    }    return -1;}int main(){    while(scanf("%d%d%d",&n,&m,&q)==3)    {        for(int i=1;i<=n;i++)        {            MAP[i][0][i][1]=MAP[i][1][i][0]=1<<q;            MAP[i][m][i][m+1]=MAP[i][m+1][i][m]=1<<q;        }        for(int j=1;j<=m;j++)        {            MAP[0][j][1][j]=MAP[1][j][0][j]=1<<q;            MAP[n][j][n+1][j]=MAP[n+1][j][n][j]=1<<q;        }        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)            {                key[i][j]=0;                for(int x=1;x<=n;x++)                    for(int y=1;y<=m;y++)                        MAP[i][j][x][y]=MAP[x][y][i][j]=0;            }        int k;        scanf("%d",&k);        int a,b,c,d,e;        while(k--)        {            scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);            if(e==0)                e=1<<q;            else                e=1<<(e-1);            MAP[a][b][c][d]=MAP[c][d][a][b]=e;        }        scanf("%d",&k);        while(k--)        {            scanf("%d%d%d",&a,&b,&c);            key[a][b]|=1<<(c-1);        }        printf("%d\n",bfs());    }    return 0;}