#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;


void getpos(int &y,int &x) {
  char c;
  scanf(" %c-%d", &c, &x);
  y=c-'a';
  x--;
}

int g[30][30][4];
int signal[30][30];

const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};

int visited[21][21][4][101];
struct P {
  int y, x, d, t;
};

int main() {
  int M,N;
  while(cin>>M>>N,M||N) {
    memset(g,0,sizeof(g));
    memset(signal,0,sizeof(signal));
    int D; cin >> D;
    int ns; cin >> ns;
    REP(i,ns) {
      int y, x;
      getpos(y,x);
      int k; cin >> k;
      signal[y][x] = k;
    }
    int nc; cin >> nc;
    REP(i,nc) {
      int y1,x1,y2,x2;
      getpos(y1,x1);
      getpos(y2,x2);
      if (y1==y2) {
        for (int x=min(x1,x2); x<max(x1,x2); ++x) {
          g[y1][x][1] = g[y1][x+1][3] = INF;
        }
      } else {
        for (int y=min(y1,y2); y<max(y1,y2); ++y) {
          g[y][x1][2] = g[y+1][x1][0] = INF;
        }
      }
    }
    int nj; cin >> nj;
    REP(i,nj) {
      int y1,x1,y2,x2;
      getpos(y1,x1);
      getpos(y2,x2);
      int d; cin >> d;
      if (y1==y2) {
        for (int x=min(x1,x2); x<max(x1,x2); ++x) {
          g[y1][x][1] = g[y1][x+1][3] = max(g[y1][x][1], d);
        }
      } else {
        for (int y=min(y1,y2); y<max(y1,y2); ++y) {
          g[y][x1][2] = g[y+1][x1][0] = max(g[y][x1][2], d);
        }
      }      
    }
    int sy,sx,gy,gx;
    getpos(sy,sx); getpos(gy,gx);
    memset(visited,0,sizeof(visited));
    queue<P> Q;
    Q.push((P){sy,sx,1,0});
    visited[sy][sx][1][0] = 1;
    
    while(!Q.empty()) {
      P p = Q.front(); Q.pop();
      // if (p.t <= 5) {
      //   cout << p.y << " "<<p.x << " " <<p.d << " " << p.t << endl;
      // }
      REP(d,4) {
        if (d == (p.d+2)%4) continue;
        int yy=p.y+dy[d];
        int xx=p.x+dx[d];
        if (yy<0||yy>=M||xx<0||xx>=N) continue;
        int tt = p.t + D + g[p.y][p.x][d];
        if (tt > 100) continue;
        if (signal[yy][xx]) {
          if ((tt / signal[yy][xx]) % 2 == 0) { // 南北
            if (d % 2 == 1) continue;
          } else {
            if (d % 2 == 0) continue;
          }
        }
        if (visited[yy][xx][d][tt]) continue;
        visited[yy][xx][d][tt] = 1;
        Q.push((P){yy,xx,d,tt});
      }
    }
    REP(t,101) {
      REP(d,4) {
        if (visited[gy][gx][d][t]) {
          cout << t << endl;
          goto nx;
        }
      }
    }
    cout << "!" << endl;
  nx:;
  }
}