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.
//**sn0wrus**//
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cout.tie(NULL);                   \
    cin.tie(NULL);
#define write(a)          \
    for (auto x : a)      \
    {                     \
        cout << x << " "; \
    }                     \
    cout << endl;
#define read(a)       \
    for (auto &x : a) \
    {                 \
        cin >> x;     \
    }
#define for0(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=n-1;i>=0;i++)
#define IN cin >>
#define OUT cout <<
#define endl "\n"
#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define pb push_back

#define fi first
#define se second

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x ;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'<<endl;}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"<<endl;}
template<typename T, typename... Args>
void __print(T t, Args... args) // recursive variadic function
{
    cout << t <<" " ;
    __print(args...) ;
}
void nl()
{
    cout<<endl;
}

using ll = long long int;
using ld = long double;
using pll = pair<ll, ll>;   
using pii = pair<int, int>;
using plll  = pair<ll,pll>;
using vll = vector<ll>;
using vi = vector<int>;

const ll MOD = (ll)(1e9) + 7LL;
const ll MM = 998244353LL;
const ll INF  = INT_MAX;

const int dir8[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
const int dir4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

const ll MAXN = 200005;

/*
for(int i=0;i<n-1;i++)
{
    int a,b;
    cin>>a>>b;
    a--,b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
}
*/

void solve()
{
	ll n,m;
    cin>>n>>m;
    map<pll,char>mp;
    set<pll>S1;
    set<pll>S2;
    while(m--)
    {
    	char op;
    	cin>>op;
    	if(op == '+')
    	{
    		ll a,b;
    		char ch;
    		cin>>a>>b>>ch;
    		mp[{a,b}] = ch;
    		if( mp.find({b,a}) != mp.end())
    		{
    			char q = mp[{b,a}];
    			S1.insert({a,b});
    			if(q==ch)
    			{
    				S2.insert({a,b});
    			}
    		}
    	}
    	else if(op=='-'){
    		ll a,b;
    		cin>>a>>b;
    		mp.erase({a,b});
    		S1.erase({b,a});
    		S1.erase({a,b});
    		S2.erase({a,b});
    		S2.erase({b,a});
    	}
    	else{
    		ll k;
    		cin>>k;
    		if(k&1)
    		{
    			if(S1.empty() && S2.empty())
    			{
    				cout<<"NO"<<endl;
    			}
    			else{
    				cout<<"YES"<<endl;
    			}
    		}
    		else{
    			if(S2.empty())
    			{
    				cout<<"NO"<<endl;
    			}
    			else{
    				cout<<"YES"<<endl;
    			}
    		}
    	}
    }
    return;
}
/*
1.check for ll for all variables. 
2.check brackets in all equation and order of conditions.
3.check custom compare funtions if any.
4.check logic carefully.
5.Dont get stuck on one approch.
*/

int main()
{
    fast;
    ll tc = 1;
    //IN tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}