Living in Byteland was good enough to begin with, but the good king decided to please his subjects and to introduce a national language. He gathered the best of wise men, and sent an expedition to faraway countries, so that they would find out all about how a language should be designed.

After some time, the wise men returned from the trip even wiser. They locked up for six months in the dining room, after which they said to the king: "there are a lot of different languages, but almost all of them have letters that are divided into vowels and consonants; in a word, vowels and consonants must be combined correctly."

There are very many rules, all of them have exceptions, but our language will be deprived of such defects! We propose to introduce a set of formal rules of combining vowels and consonants, and include in the language all the words that satisfy them.

The rules of composing words are:

  * The letters are divided into vowels and consonants in some certain way;
  * All words have a length of exactly n;
  * There are m rules of the form (pos1, t1, pos2, t2). Each rule is: if the position pos1 has a letter of type t1, then the position pos2 has a letter of type t2.



You are given some string s of length n, it is not necessarily a correct word of the new language. Among all the words of the language that lexicographically not smaller than the string s, find the minimal one in lexicographic order.

Input

The first line contains a single line consisting of letters 'V' (Vowel) and 'C' (Consonant), determining which letters are vowels and which letters are consonants. The length of this string l is the size of the alphabet of the new language (1 ≤ l ≤ 26). The first l letters of the English alphabet are used as the letters of the alphabet of the new language. If the i-th character of the string equals to 'V', then the corresponding letter is a vowel, otherwise it is a consonant.

The second line contains two integers n, m (1 ≤ n ≤ 200, 0 ≤ m ≤ 4n(n - 1)) — the number of letters in a single word and the number of rules, correspondingly.

Next m lines describe m rules of the language in the following format: pos1, t1, pos2, t2 (1 ≤ pos1, pos2 ≤ n, pos1 ≠ pos2, <image> 'V', 'C' }).

The last line contains string s of length n, consisting of the first l small letters of the English alphabet.

It is guaranteed that no two rules are the same.

Output

Print a smallest word of a language that is lexicographically not smaller than s. If such words does not exist (for example, if the language has no words at all), print "-1" (without the quotes).

Examples

Input

VC
2 1
1 V 2 C
aa


Output

ab


Input

VC
2 1
1 C 2 V
bb


Output

-1


Input

VCC
4 3
1 C 2 V
2 C 3 V
3 V 4 V
abac


Output

acaa

Note

In the first test word "aa" is not a word of the language, but word "ab" is.

In the second test out of all four possibilities only word "bb" is not a word of a language, but all other words are lexicographically less, so there is no answer.

In the third test, due to the last rule, "abac" doesn't belong to the language ("a" is a vowel, "c" is a consonant). The only word with prefix "ab" that meets the given rules is "abaa". But it is less than "abac", so the answer will be "acaa"
//Created by Aminul on 10/1/2019.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class CF569E_2__2 {
    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        char[] alphabet = in.next().toCharArray();
        boolean map[] = new boolean[256];
        int sz = alphabet.length;
        ArrayDeque<Character>[] chars = new ArrayDeque[2];
        chars[0] = new ArrayDeque<>();
        chars[1] = new ArrayDeque<>();
        for (int i = 'a', j = 0; j < alphabet.length && i <= 'z'; i++, j++) {
            map[i] = (alphabet[j] == 'V');
            if (map[i]) chars[1].addLast((char) i);
            else chars[0].addLast((char) i);
        }

        char minVowel = chars[1].size() > 0 ? chars[1].getFirst() : 0;
        char minCons = chars[0].size() > 0 ? chars[0].getFirst() : 0;
        char minChar = (char) min(minCons, minVowel);
        char maxChar = (char) max(minCons, minVowel);

        int n = in.nextInt(), m = in.nextInt();

        Node node[] = new Node[m];
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            char op1 = in.next().charAt(0);
            int v = in.nextInt();
            char op2 = in.next().charAt(0);
            u--;
            v--;
            node[i] = new Node(op1 == 'V', u, op2 == 'V', v);
        }

        String str = in.next();
        char s[] = str.toCharArray();
        String ans = null;
        char[] tmp = s.clone();

        TwoSat sat = new TwoSat(n);
        for (Node nd : node) {
            sat.addImpl(nd.bu, nd.u, nd.bv, nd.v);
        }
        for (int k = 0; k < n; k++) {
            sat.addForce(k, map[s[k]]);
        }

        int ptr = -1;
        LOOP:
        for (int i = n - 1; i >= 0; i--) {
            sat.removeLastImpl();
            boolean vowel = false, cons = false;
            for (int c = (i == n - 1) ? s[i] : s[i] + 1, j = (i == n - 1) ? s[i] - 'a' : s[i] - 'a' + 1; j < sz && c <= 'z'; c++, j++) {
                if (c > s[i]) {
                    if (map[c] && vowel) continue;
                    if (!map[c] && cons) continue;
                    if (map[c]) vowel = true;
                    if (!map[c]) cons = true;
                }
                sat.addForce(i, map[c]);
                boolean ok = sat.solve();
                sat.removeLastImpl();
                if (ok) {
                    tmp[i] = (char) c;
                    ptr = i;
                    sat.addForce(i, map[c]);
                    break LOOP;
                }
                if (vowel && cons) break;
            }
        }

        boolean ok = true;
        for (int i = ptr + 1; i < n && ptr != -1 && ok; i++) {
            boolean curr = false;

            if(minChar > 0 ) {
                sat.addForce(i, map[minChar]);
                if(sat.solve()) {
                    curr = true;
                    tmp[i] = minChar;
                } else {
                    sat.removeLastImpl();
                }
            }
            if(!curr && maxChar > 0) {
                sat.addForce(i, map[maxChar]);
                if(sat.solve()) {
                    curr = true;
                    tmp[i] = maxChar;
                } else {
                    sat.removeLastImpl();
                }
            }

            ok &= curr;
        }

        if (ptr != -1 && ok) ans = String.copyValueOf(tmp);
        if (ans == null) pw.println(-1);
        else pw.println(ans);

        pw.close();
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class Node {
        int u, v;
        boolean bu, bv;

        Node(boolean op1, int U, boolean op2, int V) {
            u = U;
            v = V;
            bu = op1;
            bv = op2;
        }
    }

    static class TwoSat {
        int n, n2;
        byte[] vals;
        SCC scc;

        public TwoSat(int nn) {
            n2 = 2 * (n = nn);
            scc = new SCC(n2);
            vals = new byte[n2];
        }

        public void removeLastImpl() {
            scc.removeLastEdge();
            scc.removeLastEdge();
        }

        // Example: (true, 0, false, 1) => 0 --> !1
        public void addImpl(boolean va, int a, boolean vb, int b) {
            a <<= 1;
            b <<= 1;
            if (!va) a++;
            if (!vb) b++;
            scc.add(a, b);
            scc.add(b ^ 1, a ^ 1);
        }

        //# Add (a NAND b)
        public void addNand(boolean va, int a, boolean vb, int b) {
            addImpl(va, a, !vb, b);
        }//$

        //# Add (a OR b)
        public void addOr(boolean va, int a, boolean vb, int b) {
            addImpl(!va, a, vb, b); // ~a -> b
        }//$

        //# Add (a XOR b)
        public void addXor(boolean va, int a, boolean vb, int b) {
            addImpl(!va, a, vb, b); // ~a -> b
            addImpl(va, a, !vb, b); // a -> ~b
        }//$

        //# Forces a to have whatever value va is
        public void addForce(int a, boolean va) {
            addImpl(!va, a, va, a);
        }//$

        // Returns the value of the variable v
        public boolean getVal(int v) {
            return vals[v << 1] == 1;
        }

        public boolean solve() {
            int map[] = scc.go();
            vals = new byte[n2];
            for (int i = 0; i < n; i++) {
                if (map[2 * i] == map[2 * i + 1]) return false;
            }
            for (int i = 0; i < n2; i++) vals[i] = (byte) -1;
            /*for (int i = 0; i < scc.size; i++) {
                for (int v : scc.comp[i]) {
                    if (vals[v] == -1) {
                        vals[v] = 1;
                    }
                    vals[v ^ 1] = (byte) (vals[v] ^ 1);
                }
            }*/
            return true;
        }
    }


    static class SCC {
        ArrayDeque<Integer>[] adj;
      //  ArrayList<Integer>[] comp;
        int n;
        int idx, size;
        boolean[] u;
        int[] pre, low, map;
        ArrayDeque<Integer> s;
        Stack<Integer> stack;

        public SCC(int nn) {
            adj = new ArrayDeque[n = nn];
            for (int curr = 0; curr < n; ++curr)
                adj[curr] = new ArrayDeque<>();
            stack = new Stack<>();
        }

        void removeLastEdge() {
            adj[stack.pop()].pollLast();
        }

        void add(int v1, int v2) {
            adj[v1].addLast(v2);
            stack.add(v1);
        }

        int[] go() {
          //  comp = new ArrayList[n];
            idx = 1;
            size = 0;
            pre = new int[n];
            low = new int[n];
            map = new int[n];
            u = new boolean[n];
            s = new ArrayDeque<Integer>();
            for (int i = 0; i < n; ++i)
                if (pre[i] == 0)
                    dfs(i);
            return map;
        }

        void dfs(int v) {
            pre[v] = low[v] = idx++;
            s.push(v);
            u[v] = true;
            for (int to : adj[v]) {
                if (pre[to] == 0) {
                    dfs(to);
                    low[v] = Math.min(low[v], low[to]);
                } else if (u[to]) {
                    low[v] = Math.min(low[v], pre[to]);
                }
            }
            if (low[v] == pre[v]) {
                int next;
               // comp[size] = new ArrayList<>();
                do {
                    next = s.pop();
                    u[next] = false;
                    map[next] = size;
                  //  comp[size].add(next);
                } while (next != v);
                size++;
            }
        }
    }
    
    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
    
        public FastReader(InputStream is) {
            this.is = is;
        }
    
        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }
    
        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    
        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }
    
        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
    
    
    
        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)){
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }
    
        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }
    
        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
    
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }
    
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    
        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }
    
        public char readChar() {
            return (char) skip();
        }
    }
}
 	  	  			   		      			  		