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"
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CNewLanguage solver = new CNewLanguage();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CNewLanguage {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] types = in.rs().toCharArray();
            for (int i = 0; i < types.length; i++) {
                types[i] = (char) (types[i] == 'V' ? 0 : 1);
            }
            int n = in.ri();
            int m = in.ri();
            Node[][] nodes = new Node[n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++) {
                    nodes[i][j] = new Node();
                    nodes[i][j].type = j;
                    nodes[i][j].index = i;
                }
            }
            for (int i = 0; i < m; i++) {
                int p1 = in.ri() - 1;
                int t1 = in.rc() == 'V' ? 0 : 1;
                int p2 = in.ri() - 1;
                int t2 = in.rc() == 'V' ? 0 : 1;
                nodes[p1][t1].out.add(nodes[p2][t2]);
                nodes[p2][t2].in.add(nodes[p1][t1]);
            }

            char[] lower = in.rs().toCharArray();
            for (int i = 0; i < n; i++) {
                lower[i] -= 'a';
            }


            int[] prefers = new int[n];
            int[] status = new int[n];
            int NOT_SET = -1;
            int V = 0;
            int C = 1;
            int DIRTY_V = 2;
            int DIRTY_C = 3;
            IntegerDeque dq = new IntegerDequeImpl(n);
            for (int start = n; start >= 0; start--) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < 2; j++) {
                        nodes[i][j].possible = false;
                    }
                }
                for (int i = 0; i < n; i++) {
                    int l = 0;
                    int r = types.length - 1;
                    if (i < start) {
                        l = r = lower[i];
                    } else if (i == start) {
                        l = lower[i] + 1;
                    }
                    for (int j = l; j <= r; j++) {
                        nodes[i][types[j]].possible = true;
                    }
                    if (l < types.length) {
                        prefers[i] = types[l];
                    }
                }
                SequenceUtils.deepFill(status, NOT_SET);
                boolean valid = true;
                for (int i = 0; i < n && valid; i++) {
                    //greedy
                    int prefer = prefers[i];
                    if (status[i] != NOT_SET) {
                        continue;
                    }
                    for (int tryTime = 0; tryTime < 2; tryTime++, prefer ^= 1) {
                        if (!nodes[i][prefer].possible) {
                            continue;
                        }
                        status[i] = prefer + 2;
                        dq.clear();
                        dq.addLast(i);
                        boolean possible = true;
                        while (!dq.isEmpty() && possible) {
                            int head = dq.removeFirst();
                            Node set = nodes[head][status[head] % 2];
                            Node notSet = nodes[head][status[head] % 2 ^ 1];
                            if (!set.possible) {
                                possible = false;
                                break;
                            }

                            for (Node x : set.out) {
                                if (status[x.index] == -1) {
                                    status[x.index] = x.type + 2;
                                    dq.addLast(x.index);
                                    continue;
                                }
                                if (status[x.index] % 2 != x.type) {
                                    possible = false;
                                    break;
                                }
                            }
                            for (Node x : notSet.in) {
                                if (status[x.index] == -1) {
                                    status[x.index] = (x.type ^ 1) + 2;
                                    dq.addLast(x.index);
                                    continue;
                                }
                                if (status[x.index] % 2 == x.type) {
                                    possible = false;
                                    break;
                                }
                            }
                        }

                        if (possible) {
                            for (int j = 0; j < n; j++) {
                                if (status[j] >= 2) {
                                    status[j] -= 2;
                                }
                            }
                            break;
                        } else {
                            for (int j = 0; j < n; j++) {
                                if (status[j] >= 2) {
                                    status[j] = -1;
                                }
                            }
                        }
                    }

                    if (status[i] == -1) {
                        valid = false;
                    }
                }

                if (valid) {
                    for (int i = 0; i < n; i++) {
                        int l = 0;
                        int r = types.length - 1;
                        if (i < start) {
                            l = r = lower[i];
                        } else if (i == start) {
                            l = lower[i] + 1;
                        }
                        for (int j = l; j <= r; j++) {
                            if (types[j] == status[i]) {
                                out.append((char) (j + 'a'));
                                break;
                            }
                        }
                    }
                    return;
                }
            }

            out.println(-1);
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static class Node {
        List<Node> in = new ArrayList<>();
        List<Node> out = new ArrayList<>();
        int type;
        int index;
        boolean possible;

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static interface IntegerStack {
        void addLast(int x);

        boolean isEmpty();

        void clear();

    }

    static interface IntegerDeque extends IntegerStack {
        int removeFirst();

    }

    static class SequenceUtils {
        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static class IntegerDequeImpl implements IntegerDeque {
        private int[] data;
        private int bpos;
        private int epos;
        private static final int[] EMPTY = new int[0];
        private int n;

        public IntegerDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            int[] newData = new int[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public IntegerIterator iterator() {
            return new IntegerIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public int next() {
                    int ans = data[index];
                    index = IntegerDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public int removeFirst() {
            int ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public void addLast(int x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public void clear() {
            bpos = epos = 0;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public boolean isEmpty() {
            return bpos == epos;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (IntegerIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public char rc() {
            return readChar();
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }
}

