#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,k,s;
int me[11][11][11][11];
int ys[11][11];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int vi[11][11][10000];
struct abc{
	int x,y,ke,bu;
};
queue <abc> q;
void bfs(){
	while(!q.empty()){
		abc ss = q.front();
		q.pop();
		if(ss.x == n&&ss.y == m){
			cout << ss.bu ;
			return;
		}
		ss.ke|=ys[ss.x][ss.y];
		if(vi[ss.x][ss.y][ss.ke]) continue;
		vi[ss.x][ss.y][ss.ke]=1;
		for (int i = 0 ; i <= 3 ; i ++){
			int x = ss.x+dx[i],y = ss.y+dy[i];
			if(x>n||x<1||y>n||y<1) continue;
			if(me[ss.x][ss.y][x][y]==-1e9) continue;
			//cout<<x<<" "<<y<<" "<<ss.ke<<" "<<me[ss.x][ss.y][x][y]<<" "<<(me[ss.x][ss.y][x][y]&ss.ke)<<endl;
			if((me[ss.x][ss.y][x][y]&ss.ke) == me[ss.x][ss.y][x][y]){
				q.push((abc){x,y,ss.ke,ss.bu+1});
				//cout<<x<<" "<<y<<" "<<ss.ke<<" "<<me[ss.x][ss.y][x][y]<<endl;
			} 
		}
		
	}
	cout << -1;
	return;
}
signed main (){ 
	cin >> n >> m >> p >> k;
	for (int i = 1 ;i <= k ; i ++){
		int x,y,xx,yy,g;
		cin >> x >> y >> xx >> yy >> g;
		if(!g) me[xx][yy][x][y] = me[x][y][xx][yy] = -1e9;
		else me[xx][yy][x][y] = me[x][y][xx][yy] = 1<<g;
	}
	cin >> s;
	for (int i = 1 ; i <= s; i++){
		int x,y,q;
		cin >> x >> y >> q;
		ys[x][y] |= 1<<(q);
	}
	q.push((abc){1,1,0,0});
	bfs();
	return 0;
}