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.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public static void solve() throws Exception {
	int n = nextInt();
	int q = nextInt();
	char[] world = next().toCharArray();
	
	LST[] lst = new LST[26];
	for(int i=0;i<lst.length;i++) {
	    lst[i] = new LST(n);
	}
	for(int i=0;i<n;i++) {
	    char ch = world[i];
	    int ind = (ch-'a');
	    lst[ind].set(i);
	}
	
	List<Integer>[] lists = new List[4];
	lists[1] = new ArrayList<Integer>(n);
	lists[2] = new ArrayList<Integer>(n);
	lists[3] = new ArrayList<Integer>(n);
	for(int i=0;i<q;i++) {
	    String sign = next();
	    int ind = nextInt();
	    if("+".equals(sign)) {
		String ch = next();
		int num = ch.charAt(0)-'a';
		lists[ind].add(num);
	    } else {
		Integer num = lists[ind].remove(lists[ind].size()-1);
	    }
	    boolean ok = true;
	    for(int[] order: new int[][]{{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}){
	    
        	    Set<Integer> toSet = new HashSet<>();
        	    ok = true;
        	    for(int r: order) {
        		int curInd = -1;
        		for(int num: lists[r]) {
        		    int next = lst[num].next(curInd + 1);
        		    if(next == -1) {
        			ok = false;
        			break;
        		    } else {
        			curInd = next;
        			lst[num].unset(next);
        			toSet.add(1000000*num + next);
        		    }
        		}
        		if(!ok) break;
        	    }
        	    for(Integer inddd: toSet) {
        		int num = inddd / 1000000;
        		int pos = inddd % 1000000;
        		lst[num].set(pos);
        	    }
        	    if(ok) {
        		break;
        	    }
	    }
	    if(ok) println("YES");
	    else println("NO");
	}
    }

    public static void main(String[] args) throws Exception {
	try {
	    fastReader = new FastReader(System.in);
	    systemOut = new BufferedOutputStream(System.out);
	    solve();
	} finally {
	    systemOut.close();
	}
    }

    private static FastReader fastReader = null;
    private static BufferedOutputStream systemOut = null;

    public static void print(Object obj) {
	print(obj.toString());
    }

    public static void print(String str) {
	try {
	    systemOut.write(str.getBytes("utf-8"));
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static void println(Object obj) {
	println(obj.toString());
    }

    public static void println(String str) {
	try {
	    print(str);
	    systemOut.write('\n');
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static String next() {
	return fastReader.readNextToken(false);
    }

    public static String nextLine() {
	return fastReader.readNextToken(true);
    }

    public static int nextInt() {
	return Integer.parseInt(fastReader.readNextToken(false));
    }

    public static long nextLong() {
	return Long.parseLong(fastReader.readNextToken(false));
    }

    public static double nextDouble() {
	return Double.parseDouble(fastReader.readNextToken(false));
    }

    public static void exit() {
	try {
	    systemOut.close();
	} catch (IOException e) {
	    // should never happen
	}
	System.exit(0);
    }

    static class FastReader {
	private byte[] buf = new byte[65536];
	private int ind = 0;
	private int maxInd = -1;
	private InputStream is = null;
	private boolean eof = false;
	private boolean lastCharRead = false;

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

	public String readNextToken(boolean endOfLine) {
	    try {
		StringBuilder sb = new StringBuilder();
		boolean found = false;
		while (true) {
		    if (lastCharRead) {
			return null;
		    } else if (ind > maxInd) {
			if (eof) {
			    lastCharRead = true;
			} else {
			    fillBuffer();
			}
		    }
		    byte b = '\n';
		    if (!lastCharRead) {
			b = buf[ind++];
		    }

		    if (b == '\r') {
			// ignore
		    } else if ((b == '\n' && endOfLine) || (Character.isWhitespace(b) && !endOfLine)) {
			if (found) {
			    break;
			}
		    } else {
			sb.append((char) b);
			found = true;
		    }
		}
		return sb.toString();
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}

	private void fillBuffer() {
	    try {
		int read = is.read(buf, 0, buf.length);
		if (read < buf.length) {
		    eof = true;
		}
		ind = 0;
		maxInd = read - 1;
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}
    }
    
    public static class LST {
	public long[][] set;
	public int n;

	public LST(int n) {
	    this.n = n;
	    int d = 1;
	    for (int m = n; m > 1; m >>>= 6, d++)
		;

	    set = new long[d][];
	    for (int i = 0, m = n >>> 6; i < d; i++, m >>>= 6) {
		set[i] = new long[m + 1];
	    }
	}

	// [0,r)
	public LST setRange(int r) {
	    for (int i = 0; i < set.length; i++, r = r + 63 >>> 6) {
		for (int j = 0; j < r >>> 6; j++) {
		    set[i][j] = -1L;
		}
		if ((r & 63) != 0)
		    set[i][r >>> 6] |= (1L << r) - 1;
	    }
	    return this;
	}

	// [0,r)
	public LST unsetRange(int r) {
	    if (r >= 0) {
		for (int i = 0; i < set.length; i++, r = r + 63 >>> 6) {
		    for (int j = 0; j < r + 63 >>> 6; j++) {
			set[i][j] = 0;
		    }
		    if ((r & 63) != 0)
			set[i][r >>> 6] &= ~((1L << r) - 1);
		}
	    }
	    return this;
	}

	public LST set(int pos) {
	    if (pos >= 0 && pos < n) {
		for (int i = 0; i < set.length; i++, pos >>>= 6) {
		    set[i][pos >>> 6] |= 1L << pos;
		}
	    }
	    return this;
	}

	public LST unset(int pos) {
	    if (pos >= 0 && pos < n) {
		for (int i = 0; i < set.length && (i == 0 || set[i - 1][pos] == 0L); i++, pos >>>= 6) {
		    set[i][pos >>> 6] &= ~(1L << pos);
		}
	    }
	    return this;
	}

	public boolean get(int pos) {
	    return pos >= 0 && pos < n && set[0][pos >>> 6] << ~pos < 0;
	}

	public LST toggle(int pos) {
	    return get(pos) ? unset(pos) : set(pos);
	}

	public int prev(int pos) {
	    for (int i = 0; i < set.length && pos >= 0; i++, pos >>>= 6, pos--) {
		int pre = prev(set[i][pos >>> 6], pos & 63);
		if (pre != -1) {
		    pos = pos >>> 6 << 6 | pre;
		    while (i > 0)
			pos = pos << 6 | 63 - Long.numberOfLeadingZeros(set[--i][pos]);
		    return pos;
		}
	    }
	    return -1;
	}

	public int next(int pos) {
	    for (int i = 0; i < set.length && pos >>> 6 < set[i].length; i++, pos >>>= 6, pos++) {
		int nex = next(set[i][pos >>> 6], pos & 63);
		if (nex != -1) {
		    pos = pos >>> 6 << 6 | nex;
		    while (i > 0)
			pos = pos << 6 | Long.numberOfTrailingZeros(set[--i][pos]);
		    return pos;
		}
	    }
	    return -1;
	}

	private static int prev(long set, int n) {
	    long h = set << ~n;
	    if (h == 0L)
		return -1;
	    return -Long.numberOfLeadingZeros(h) + n;
	}

	private static int next(long set, int n) {
	    long h = set >>> n;
	    if (h == 0L)
		return -1;
	    return Long.numberOfTrailingZeros(h) + n;
	}

	@Override
	public String toString() {
	    List<Integer> list = new ArrayList<Integer>();
	    for (int pos = next(0); pos != -1; pos = next(pos + 1)) {
		list.add(pos);
	    }
	    return list.toString();
	}
    }
}
