You are given a directed graph consisting of n vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.

You should process m queries with it. Each query is one of three types: 

  * "+ u v c" — add arc from u to v with label c. It's guaranteed that there is no arc (u, v) in the graph at this moment; 
  * "- u v" — erase arc from u to v. It's guaranteed that the graph contains arc (u, v) at this moment; 
  * "? k" — find the sequence of k vertices v_1, v_2, ..., v_k such that there exist both routes v_1 → v_2 → ... → v_k and v_k → v_{k - 1} → ... → v_1 and if you write down characters along both routes you'll get the same string. You can visit the same vertices any number of times. 

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices in the graph and the number of queries.

The next m lines contain queries — one per line. Each query is one of three types: 

  * "+ u v c" (1 ≤ u, v ≤ n; u ≠ v; c is a lowercase Latin letter); 
  * "- u v" (1 ≤ u, v ≤ n; u ≠ v); 
  * "? k" (2 ≤ k ≤ 10^5). 



It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.

Output

For each query of the third type, print YES if there exist the sequence v_1, v_2, ..., v_k described above, or NO otherwise.

Example

Input


3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5


Output


YES
NO
YES

Note

In the first query of the third type k = 3, we can, for example, choose a sequence [1, 2, 3], since 1 \xrightarrow{a} 2 \xrightarrow{b} 3 and 3 \xrightarrow{a} 2 \xrightarrow{b} 1.

In the second query of the third type k = 2, and we can't find sequence p_1, p_2 such that arcs (p_1, p_2) and (p_2, p_1) have the same characters.

In the third query of the third type, we can, for example, choose a sequence [1, 2, 3, 2, 1], where 1 \xrightarrow{a} 2 \xrightarrow{b} 3 \xrightarrow{d} 2 \xrightarrow{c} 1.
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    public  void solve() throws IOException 
    {
 
        //int t = readInt();


 
         int n = readInt();
         int m  = readInt();
         HashSet<Long> glob = new HashSet<Long>(m);

         HashSet<Long> loc[]=new HashSet[26];

          for(int i =0;i<26;i++)
          {
            loc[i]=new HashSet<Long>(m);
          }

          int globmatch=0;
          int local=0;




         
         for(int f =0;f<m;f++)
         {
            String a = readString();
            if(a.charAt(0)=='+')
            {
                 int u = readInt();
                 int v = readInt();
                 String b = readString();
                 int c = (int)b.charAt(0)-97;
                 long hash1 = hash(u,v);
                 long hash2 = hash(v,u);
                 loc[c].add(hash1);
                 if(loc[c].contains(hash2))
                 {
                    local++;
                 }

                 glob.add(hash1);
                 if(glob.contains(hash2))
                 {
                     globmatch++;
                 }
            }   
            else if(a.charAt(0)=='-')
            {
                int u = readInt();
                int v = readInt();
                 long hash1 = hash(u,v);
                 long hash2 = hash(v,u);
                 for(int c =0;c<26;c++){
                  if(loc[c].contains(hash1)){
                   loc[c].remove(hash1);

                   if(loc[c].contains(hash2))
                   {
                    local--;
                   }
                   }
                 }
                 glob.remove(hash1);
                 if(glob.contains(hash2))
                 {
                     globmatch--;
                 }

            }
            else
            {
                int k = readInt();
                if(k%2==0)
                {
                    if(local>0)
                        out.println("YES");
                    else
                        out.println("NO");
                }
                else
                {
                     if(globmatch>0)
                        out.println("YES");
                     else
                        out.println("NO");
                }

            }
         }

      


      
       
    }
    public long hash(int u , int v )
    {

        long gal = (long)u*(300000);
        gal = gal+v;
        return gal;
    }

    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);
 
    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int f ;
    int e;
    int val;
    
    edge(int u, int v, int val)
    {
       this.f=u;
       this.e=v;
       this.val= val;
    }
    public int compareTo(edge e)
    {
        return this.e-e.e;
    }
}