During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.

The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.

The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: 1, 2, 3, so that each character is painted in at most one color, and the description of the i-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color i.

The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.

Input

The first line of the input contains two integers n, q (1 ≤ n ≤ 100 000, 1 ≤ q ≤ 1000) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length n consisting of lowercase English characters.

Each of the following line describes a single evolution and is in one of the following formats: 

  * + i c (i ∈ \{1, 2, 3\}, c ∈ \{a, b, ..., z\}: append the character c to the end of i-th religion description. 
  * - i (i ∈ \{1, 2, 3\}) – remove the last character from the i-th religion description. You can assume that the pattern is non-empty. 



You can assume that no religion will have description longer than 250 characters.

Output

Write q lines. The i-th of them should be YES if the religions could coexist in peace after the i-th evolution, or NO otherwise.

You can print each character in any case (either upper or lower).

Examples

Input


6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2


Output


YES
YES
YES
YES
YES
YES
NO
YES


Input


6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z


Output


YES
YES
YES
YES
YES
NO
YES
NO

Note

In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe:

<image>
1 1
t
+ 2 p
 2 12
aa
+ 1 a
+ 2 a
+ 3 a
- 1
+ 1 a
- 2
+ 2 a
- 3
+ 3 a
+ 2 a
- 1
- 3
 2 10
uh
+ 1 h
+ 2 u
+ 3 h
- 1
- 2
+ 2 h
+ 3 u
- 2
+ 1 u
- 3
 1 1
z
+ 3 z

NO
 YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
 YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
 YES

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.io.FilterInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DThreeReligions solver = new DThreeReligions();
        solver.solve(1, in, out);
        out.close();
    }

    static class DThreeReligions {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int q = in.scanInt();
            String world = in.scanString().toLowerCase();
            StringBuffer[] sb = new StringBuffer[4];
            sb[0] = new StringBuffer("");
            sb[1] = new StringBuffer("");
            sb[3] = new StringBuffer("");
            sb[2] = new StringBuffer("");
            AVLTree<Integer> arrayList[] = new AVLTree[26];
            for (int i = 0; i < 26; i++) arrayList[i] = new AVLTree<>(true);
            for (int i = 0; i < n; i++) arrayList[world.charAt(i) - 'a'].insert(i);
            while (q-- > 0) {
                char type = in.scanChar();
                if (type == '+') {
                    int nu = in.scanInt();
                    char xx = in.scanChar();
                    sb[nu].append(xx);
                } else if (type == '-') {
                    int nu = in.scanInt();
                    if (sb[nu].length() == 0) throw new RuntimeException("ERROR");
                    sb[nu].deleteCharAt(sb[nu].length() - 1);
                }


                boolean final_ans = false;


                int sldjfs[][] = new int[6][3];
                sldjfs[0] = new int[]{1, 2, 3};
                sldjfs[1] = new int[]{1, 3, 2};
                sldjfs[2] = new int[]{2, 1, 3};
                sldjfs[3] = new int[]{2, 3, 1};
                sldjfs[4] = new int[]{3, 2, 1};
                sldjfs[5] = new int[]{3, 1, 2};


                for (int te = 0; te < 6; te++) {
                    boolean f = true;
                    ArrayList<Integer> p[] = new ArrayList[4];
                    for (int i = 0; i < 4; i++) p[i] = new ArrayList<>();
                    int per[] = sldjfs[te];
                    for (int kk = 0; kk < 3; kk++) {
                        int inde = per[kk];
                        for (int i = 0; i < sb[inde].length(); i++) {
                            int c = sb[inde].charAt(i) - 'a';
                            int temp = (p[inde].size() > 0) ? p[inde].get(p[inde].size() - 1) : -1;
                            int k = (int) arrayList[c].lower_bound(temp + 1);
                            if (k != arrayList[c].getSize()) {
                                int pos = arrayList[c].getAtIndex(k);
                                p[inde].add(pos);
                                arrayList[c].remove(pos);
                            } else {
                                f = false;
                            }
                        }
                    }
                    for (int i = 1; i <= 3; i++) {
                        for (int k : p[i]) {
                            int c = world.charAt(k) - 'a';
                            arrayList[c].insert(k);

                        }
                    }
                    final_ans |= f;
                }


                if (final_ans) {
                    out.println("YES");
                } else {
                    out.println("NO");
                }


            }


        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public char scanChar() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            return (char) c;
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        public String scanString() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            StringBuilder RESULT = new StringBuilder();
            do {
                RESULT.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return RESULT.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }

    static class AVLTree<T extends Comparable<? super T>> {
        private Node<T> root;
        private boolean multi;
        private Node<T> tempNode;

        public AVLTree() {
            this.root = null;
            this.multi = false;
        }

        public AVLTree(boolean multi) {
            this.root = null;
            this.multi = multi;
        }

        public T getAtIndex(int i) {

            if (i < 0 || i >= getSize()) return null;

            tempNode = root;
            int current = 0;
            while (tempNode != null) {
                if (tempNode.left == null) {
                    if (current + tempNode.count <= i) {
                        current += tempNode.count;
                        tempNode = tempNode.right;
                    } else {
                        return tempNode.data;
                    }
                } else {

                    if (tempNode.leftcount + current > i) {
                        tempNode = tempNode.left;
                    } else if (tempNode.leftcount + tempNode.count + current <= i) {
                        current += tempNode.count + tempNode.leftcount;
                        tempNode = tempNode.right;
                    } else return tempNode.data;

                }
            }
            return null;
        }

        public long getSize() {
            if (root == null) return 0;
            else {
                return root.leftcount + root.rightcount + root.count;
            }
        }

        public void insert(T data, int... count) {
            if (count.length == 0) root = insert(data, root, 1);
            else {
                if (count[0] > 0) root = insert(data, root, count[0]);
            }
        }

        private Node<T> insert(T data, Node<T> tempRoot, int count) {
            if (tempRoot == null) {
                if (!multi) {

                    return new Node<>(data);
                } else {

                    return new Node<>(data, count);
                }
            }


            int compartor = data.compareTo(tempRoot.data);
            if (compartor < 0) {
                tempRoot.left = insert(data, tempRoot.left, count);
            } else if (compartor > 0) {
                tempRoot.right = insert(data, tempRoot.right, count);
            } else {
                if (multi) {
                    tempRoot.count += count;
                }
            }


            tempRoot.leftcount = getLeftCount(tempRoot.left) + getRightCount(tempRoot.left) + getCount(tempRoot.left);
            tempRoot.rightcount = getLeftCount(tempRoot.right) + getRightCount(tempRoot.right) + getCount(tempRoot.right);


            tempRoot.height = Math.max(Hieght(tempRoot.left), Hieght(tempRoot.right)) + 1;


            long diff = getBalence(tempRoot);

            if (diff > 1) {
                if (data.compareTo(tempRoot.left.data) < 0) {
                    return rotateRight(tempRoot);
                } else {
                    tempRoot.left = rotateLeft(tempRoot.left);
                    return rotateRight(tempRoot);
                }
            } else if (diff < -1) {
                if (data.compareTo(tempRoot.right.data) > 0) {
                    return rotateLeft(tempRoot);
                } else {
                    tempRoot.right = rotateRight(tempRoot.right);
                    return rotateLeft(tempRoot);
                }
            }

            return tempRoot;


        }

        public Node<T> rotateRight(Node<T> node) {
            Node<T> x = node.left;
            Node<T> t2 = x.right;


            x.right = node;
            node.left = t2;


            node.height = Math.max(Hieght(node.right), Hieght(node.left)) + 1;
            x.height = Math.max(Hieght(x.left), Hieght(x.right)) + 1;


            node.leftcount = getLeftCount(node.left) + getRightCount(node.left) + getCount(node.left);
            node.rightcount = getLeftCount(node.right) + getRightCount(node.right) + getCount(node.right);


            x.leftcount = getLeftCount(x.left) + getRightCount(x.left) + getCount(x.left);
            x.rightcount = getLeftCount(x.right) + getRightCount(x.right) + getCount(x.right);

            return x;

        }

        public Node<T> rotateLeft(Node<T> node) {
            Node<T> x = node.right;
            Node<T> t2 = x.left;


            x.left = node;
            node.right = t2;


            node.height = Math.max(Hieght(node.right), Hieght(node.left)) + 1;
            x.height = Math.max(Hieght(x.left), Hieght(x.right)) + 1;


            node.leftcount = getLeftCount(node.left) + getRightCount(node.left) + getCount(node.left);
            node.rightcount = getLeftCount(node.right) + getRightCount(node.right) + getCount(node.right);


            x.leftcount = getLeftCount(x.left) + getRightCount(x.left) + getCount(x.left);
            x.rightcount = getLeftCount(x.right) + getRightCount(x.right) + getCount(x.right);

            return x;

        }

        public long getLeftCount(Node<T> node) {
            if (node == null) return 0;
            return node.leftcount;
        }

        public long getRightCount(Node<T> node) {
            if (node == null) return 0;
            return node.rightcount;
        }

        public long getCount(Node<T> node) {
            if (node == null) return 0;
            return node.count;
        }

        long getBalence(Node<T> node) {
            if (node == null)
                return 0;

            return Hieght(node.left) - Hieght(node.right);
        }

        public long Hieght(Node<T> Node) {
            if (Node == null) return 0;
            else return Node.height;
        }

        public void remove(T data) {
            root = remove(root, data, 1);
        }

        private Node<T> remove(Node<T> tempRoot, T data, long num) {


            if (tempRoot == null) return null;
            int compartor = data.compareTo(tempRoot.data);
            if (compartor < 0) {
                tempRoot.left = remove(tempRoot.left, data, num);
            } else if (compartor > 0) {
                tempRoot.right = remove(tempRoot.right, data, num);
            } else {
                if (multi && num < tempRoot.count && tempRoot.count > 1) {
                    tempRoot.count -= num;
                } else {
                    if (tempRoot.left == null && tempRoot.right == null) {
                        return null;
                    } else if (tempRoot.left == null) return tempRoot.right;
                    else if (tempRoot.right == null) return tempRoot.left;
                    else {
                        Node<T> minValueNode = getMinValueNode(tempRoot.right);

                        tempRoot.data = minValueNode.data;
                        tempRoot.count = minValueNode.count;

                        tempRoot.right = remove(tempRoot.right, tempRoot.data, tempRoot.count);
                    }

                }
            }


            tempRoot.leftcount = getLeftCount(tempRoot.left) + getRightCount(tempRoot.left) + getCount(tempRoot.left);
            tempRoot.rightcount = getLeftCount(tempRoot.right) + getRightCount(tempRoot.right) + getCount(tempRoot.right);

            tempRoot.height = Math.max(Hieght(tempRoot.left), Hieght(tempRoot.right)) + 1;


            long diff = getBalence(tempRoot);

            if (diff > 1) {
                if (getBalence(tempRoot.left) >= 0) {
                    return rotateRight(tempRoot);
                } else {
                    tempRoot.left = rotateLeft(tempRoot.left);
                    return rotateRight(tempRoot);
                }
            } else if (diff < -1) {
                if (getBalence(tempRoot.right) <= 0) {
                    return rotateLeft(tempRoot);
                } else {
                    tempRoot.right = rotateRight(tempRoot.right);
                    return rotateLeft(tempRoot);
                }
            }

            return tempRoot;
        }

        public Node<T> getMinValueNode(Node<T> node) {
            if (node == null) return null;
            Node<T> currentNode = node;
            while (currentNode.left != null) {
                currentNode = currentNode.left;
            }
            return currentNode;
        }

        public long lower_bound(T data) {
            tempNode = root;
            long index = 0;
            while (tempNode != null) {
                int comparator = data.compareTo(tempNode.data);
                if (comparator < 0) {
                    tempNode = tempNode.left;
                } else if (comparator > 0) {
                    index += (tempNode.count + tempNode.leftcount);
                    tempNode = tempNode.right;
                } else {
                    index += tempNode.leftcount;
                    break;
                }
            }

            return index;
        }

        public class Node<T> {
            T data;
            long height;
            Node<T> left;
            Node<T> right;
            long leftcount;
            long rightcount;
            long count;

            public Node(T data) {
                this.data = data;
                this.height = 1;
                this.left = null;
                this.right = null;
                this.leftcount = 0;
                this.rightcount = 0;
                this.count = 1;
            }

            public Node(T data, int count) {
                this.data = data;
                this.height = 1;
                this.left = null;
                this.right = null;
                this.leftcount = 0;
                this.rightcount = 0;
                this.count = count;
            }

        }

    }
}

