#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>using namespace std;struct point{    int x,y,counts,mykey;}start;int n,m,p,k,s,flag,door[55][55][55][55],key[55][55],vis[55][55][2048],dir[4][2] = {-1,0,0,-1,1,0,0,1};int main(){    while(~scanf("%d%d%d",&n,&m,&p))    {        memset(door,-1,sizeof(door));        memset(key,0,sizeof(key));        memset(vis,0,sizeof(vis));        scanf("%d",&k);        int x1,y1,x2,y2,type;        while(k--)        {            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&type);            door[x1][y1][x2][y2] = type;            door[x2][y2][x1][y1] = type;        }        scanf("%d",&s);        int x,y,keytype;        while(s--)        {            scanf("%d%d%d",&x,&y,&keytype);            key[x][y] |= 1<<(keytype-1);        }        queue<point> q;        start.x = 1;        start.y = 1;        start.counts = 0;        start.mykey = key[1][1];        vis[1][1][start.mykey] = 1;        q.push(start);        flag = 1;        while(!q.empty())        {            point now = q.front();            q.pop();            if(now.x == n && now.y == m)            {                flag = 0;                printf("%d\n",now.counts);                break;            }            for(int i = 0;i < 4;i++)            {                point temp;                temp.x = now.x+dir[i][0];                temp.y = now.y+dir[i][1];                if(temp.x < 1 || temp.x > n || temp.y < 1 || temp.y > m)    continue;                if(door[now.x][now.y][temp.x][temp.y] != -1 &&(now.mykey & 1<<(door[now.x][now.y][temp.x][temp.y]-1)) == 0)  continue;                temp.counts = now.counts+1;                temp.mykey = now.mykey | key[temp.x][temp.y];                if(vis[temp.x][temp.y][temp.mykey]) continue;                vis[temp.x][temp.y][temp.mykey] = 1;                q.push(temp);            }        }        if(flag)    printf("-1\n");    }}