#include <bits/stdc++.h>   using namespace std;   const string str =  VC ;   const int maxn = 300;   char s[2];   int l, n, m;   char buf[maxn];   int alpha[26];   vector<int> G[maxn * 2];   bool mark[maxn * 2];   int stk[maxn * 2], top;   bool dfs(int u) {     if (s[u & 1] == 0) return false;     if (mark[u ^ 1]) return false;     if (mark[u]) return true;     while (top == 2 * maxn)       ;     mark[stk[top++] = u] = true;     for (int v : G[u])       if (!dfs(v)) return false;     return true;   }   string ans;   void check(string tmp) {     if (ans ==    || tmp < ans) ans = tmp;   }   void solve(int st) {     for (int i = 0; i < 2 * n; i++) mark[i] = 0;     for (int i = 0; i < st; i++) {       top = 0;       if (!dfs(i << 1 | alpha[buf[i] -  a ])) return;     }     for (int i = 2 * st; i < 2 * n; i += 2) {       if (mark[i] || mark[i ^ 1]) continue;       top = 0;       if (s[0] < s[1]) {         if (!dfs(i)) {           while (top) mark[stk[--top]] = false;           if (!dfs(i ^ 1)) return;         }       } else {         if (!dfs(i ^ 1)) {           while (top) mark[stk[--top]] = false;           if (!dfs(i)) return;         }       }     }     string tmp(buf, buf + st);     for (int i = st; i < n; i++) tmp += s[mark[i << 1 | 1]];     check(tmp);   }   int main() {     scanf( %s , buf);     l = strlen(buf);     for (int i = l - 1; i >= 0; i--) s[alpha[i] = str.find(buf[i])] =  a  + i;     scanf( %d %d , &n, &m);     for (int i = 0; i < m; i++) {       int x, y;       scanf( %d %s , &x, buf);       x--;       x = x << 1 | str.find(buf[0]);       scanf( %d %s , &y, buf);       y--;       y = y << 1 | str.find(buf[0]);       G[x].push_back(y);       G[y ^ 1].push_back(x ^ 1);     }     scanf( %s , buf);     for (int i = 0; i <= n; i++) {       if (i < n) {         char ch = buf[i];         for (buf[i]++; buf[i] <  a  + l; buf[i]++) solve(i + 1);         buf[i] = ch;       } else         solve(n);     }     if (ans !=   )       puts(ans.c_str());     else       puts( -1 );   }   