#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000005

class RollingHash{
public:
  typedef unsigned long long ull;
  ull B = 1777771; //ハッシュ基数
  int n;
  string s;
  vector<ull> hash;
  vector<ull> k;

  RollingHash(){};
  RollingHash(string s):n(s.size()),s(s),hash(n+1),k(n+1){
    for(int i=0;i<n;i++) hash[i+1] = hash[i] * B + s[i];
    k[0] = 1;
    for(int i=1;i<=n;i++) k[i] = k[i-1] * B;
  }

  ull get(int l,int r){assert(0<=l && r<=n);return hash[r] - hash[l] * k[r-l];}//[l,r)
};

class RMQ{
public : 
  typedef pair<int,int> P;
  typedef long long ll;
  const ll INF = 1LL<<55;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n;
  vector<ll> dat;
  vector<data> td;
  
  RMQ(){n=-1;}
  RMQ(int n_){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)の値をxに変更 update(a,b,x)
  ll update(int a,int b,int x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a < n && b <= n);
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      dat[k*2+1]=dat[k*2+2]=td[k].value;
      td[k*2+1]=td[k*2+2]=(data){1,td[k].value};
      td[k].type=0;
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)の最小値を得る find(a,b);
  ll find(int a,int b){return update(a,b,0,false);};
};

//Suffix_Array
//O(|T|log|S|) Sの文字列からTの文字列があるか検索
#define rank Asadfsadfs

class SA{
public:
  int Len,n;
  vector<int> rank;
  vector<int> tmp;
  vector<int> sa;
  string S;
  RollingHash A;
  
  SA(){
    rank.resize(MAX_N+1);
    tmp.resize(MAX_N+1);
    sa.resize(MAX_N+1);
  }
  
  //(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
  bool compare_sa(int i,int j){
    if(rank[i]!=rank[j])return rank[i]<rank[j];
    int ri=i+Len<=n?rank[i+Len]:-1;
    int rj=j+Len<=n?rank[j+Len]:-1;
    return ri<rj;
  }
  
  //文字列Sの接尾辞配列を構築
  void construct_sa(string S){
    A = RollingHash(S);
    this->S = S;
    n=S.length();
    //最初は一文字、ランクは文字コードにする
    for(int i=0;i<=n;i++){
      sa[i]=i;
      rank[i]=i<n?S[i]:-1;
    }
    //k文字についてソートされているところから、2k文字でソート
    for(Len=1;Len<=n;Len*=2){
      sort(sa.begin(),sa.begin()+n+1,[&] (int i,int j){
          if(rank[i]!=rank[j])return rank[i]<rank[j];
          int ri=i+Len<=n?rank[i+Len]:-1;
          int rj=j+Len<=n?rank[j+Len]:-1;
          return ri<rj;
        });
      //いったんtmpに次のランクを計算して、rankに代入
      tmp[sa[0]]=0;
      for(int i=1;i<=n;i++)
        tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
      for(int i=0;i<=n;i++)rank[i]=tmp[i];
    }
  }

  //Sの文字列からTの文字列があるか検索する
  bool contain(string S,string T){
    int left=0,right=S.length();
    while(right-left>1){
      int mid=(left+right)/2;
      if(S.compare(sa[mid],T.length(),T)<0)left=mid;
      else right=mid;
    }
    return S.compare(sa[right],T.length(),T)==0;
  }
  
  int compare(int a,int b,int n,RollingHash &A ,RollingHash &B,string &T){
    int L = 0, R = n;
    while(L+1<R){
      int M = (L+R)/2;
      if(a + M > (int)S.size() || A.get(a,a+M) != B.get(b,b+M)) R = M;
      else L = M;
    }

    if(L == n) return 1;
    if(S[a+L] < T[b+L]) return -1;
    return 1;
  }

  int Lower(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>=0) R = M;
      //if(S.compare(sa[M],T.size(),T)>=0) R = M;
      else L = M+1;
    }  
    return L;
  }
  
  int Upper(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>0) R = M;
      //if(S.compare(sa[M],T.size(),T)>0) R = M;
      else L = M+1;
    }
    
    return L;
  }

};

string s, p[100005];
SA sa = SA();

int Lower(string t){
  
  int l = 0, r = (int)s.size() + 1;
  
  while( l + 1 < r ){
    
    int m = ( l + r ) / 2;
    int idx = sa.sa[m];
    
    if( s.substr(idx) < t ) l = m;
    else r = m;
    
  }

  return r;
} // sa で　初めてt以上になるところのidx

typedef pair<int,int> P;

int n;

int main(){
  
  cin>>s;

  cin>>n;
  
  for(int i=0;i<n;i++) cin>>p[i];
  
  sort( p, p+n, [](const string &a,const string &b){
      return a.size() > b.size();
    });
  
  sa.construct_sa(s);
  
  int len = s.size();
  
  RMQ rmq = RMQ(len+1);
  
  for(int i=0;i<len+1;i++) rmq.update(i,i+1,0);
  
  for(int i=0;i<n;i++){
    
    string t = p[i];

    int L = Lower( t ), R = Lower( t + '{' );
    
    if( L == R || L >= len + 1 ) continue;
    
    rmq.update( Lower(t), Lower(t+'{'), (int)t.size() );
    
  }
  
  vector<P> v;
  
  for(int i=1;i<len+1;i++){
    
    v.push_back(P( rmq.find( i, i+1 ) + sa.sa[i] - 1 , sa.sa[i] ));
    
  }
  
  sort(v.begin(), v.end());
  
  int ans = 0, maxr = -1;
  
  for(int i=0;i<len;i++){
    
    int l = v[i].second, r = v[i].first;
    
    if( l > r ) continue;
    
    if( maxr < l ){
      ans++;
      maxr = r;
    }
    
  }
  
  cout<<ans<<endl;
  
  return 0;
}


### Prompt

Create a solution in Cpp for the following problem:

G： 検閲により置換 (Censored String)

Problem Statement

You are given the string S, and the set of strings \mathcal P whose size is N. Now we consider applying the following operation to S:

* Choose exactly one character in S, and replace it with '*'.



Let s_i be a i-th character of S, S_{ij} be a consecutive substring in S such that  S = s_i s_{i+1} $\cdots$  s_j, and p_k as the k-th string of P. Your task is to calculate the minimum number of operations for satisfying the following condition.

* For all pairs (S_{ij}, p_k), it is satisfied that S_{ij} \neq p_k.



Input

An input is given in the following format.


S
N
p_1
p_2
$\vdots$
p_N


* In line 1, you are given the string S.
* In line 2, given an integer N. N means the size of P.
* From line 3 to the end, given p_i, the i-th string of P.



Constraints

* 1 \leq |S| \leq 10^5
* 1 \leq N \leq 10^5
* 1 \leq |p_1| + |p_2| +  $\cdots$  + |p_N| \leq 10^5
* If i \neq j, it is guaranteed that p_i \neq p_j
* S, and p_i include lowercase letters only



Output

Print the minimum number of operations in one line.

Sample Input 1


brainfuck
1
fuck


Sample Output 1


1

For example, if you change "brainfuck" into "brainf*ck", you can satisfy the condition. You have to perform operation at least once, and it is the minimum value.

Sample Input 2


aaa
1
a


Sample Output 2


3

You have to operate for all characters.

Sample Input 3


hellshakeyano
3
hell
shake
key


Sample Output 3


2

In this case, for example, if you change "hellshakeyano" into "h*llsha*eyano", you can satisfy the condition. Notice if you replace one character, it might happen that several strings in the set P, which appear as the consecutive substring of S, simultaneously disappear.





Example

Input

brainfuck
1
fuck


Output

1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000005

class RollingHash{
public:
  typedef unsigned long long ull;
  ull B = 1777771; //ハッシュ基数
  int n;
  string s;
  vector<ull> hash;
  vector<ull> k;

  RollingHash(){};
  RollingHash(string s):n(s.size()),s(s),hash(n+1),k(n+1){
    for(int i=0;i<n;i++) hash[i+1] = hash[i] * B + s[i];
    k[0] = 1;
    for(int i=1;i<=n;i++) k[i] = k[i-1] * B;
  }

  ull get(int l,int r){assert(0<=l && r<=n);return hash[r] - hash[l] * k[r-l];}//[l,r)
};

class RMQ{
public : 
  typedef pair<int,int> P;
  typedef long long ll;
  const ll INF = 1LL<<55;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n;
  vector<ll> dat;
  vector<data> td;
  
  RMQ(){n=-1;}
  RMQ(int n_){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)の値をxに変更 update(a,b,x)
  ll update(int a,int b,int x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a < n && b <= n);
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      dat[k*2+1]=dat[k*2+2]=td[k].value;
      td[k*2+1]=td[k*2+2]=(data){1,td[k].value};
      td[k].type=0;
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)の最小値を得る find(a,b);
  ll find(int a,int b){return update(a,b,0,false);};
};

//Suffix_Array
//O(|T|log|S|) Sの文字列からTの文字列があるか検索
#define rank Asadfsadfs

class SA{
public:
  int Len,n;
  vector<int> rank;
  vector<int> tmp;
  vector<int> sa;
  string S;
  RollingHash A;
  
  SA(){
    rank.resize(MAX_N+1);
    tmp.resize(MAX_N+1);
    sa.resize(MAX_N+1);
  }
  
  //(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
  bool compare_sa(int i,int j){
    if(rank[i]!=rank[j])return rank[i]<rank[j];
    int ri=i+Len<=n?rank[i+Len]:-1;
    int rj=j+Len<=n?rank[j+Len]:-1;
    return ri<rj;
  }
  
  //文字列Sの接尾辞配列を構築
  void construct_sa(string S){
    A = RollingHash(S);
    this->S = S;
    n=S.length();
    //最初は一文字、ランクは文字コードにする
    for(int i=0;i<=n;i++){
      sa[i]=i;
      rank[i]=i<n?S[i]:-1;
    }
    //k文字についてソートされているところから、2k文字でソート
    for(Len=1;Len<=n;Len*=2){
      sort(sa.begin(),sa.begin()+n+1,[&] (int i,int j){
          if(rank[i]!=rank[j])return rank[i]<rank[j];
          int ri=i+Len<=n?rank[i+Len]:-1;
          int rj=j+Len<=n?rank[j+Len]:-1;
          return ri<rj;
        });
      //いったんtmpに次のランクを計算して、rankに代入
      tmp[sa[0]]=0;
      for(int i=1;i<=n;i++)
        tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
      for(int i=0;i<=n;i++)rank[i]=tmp[i];
    }
  }

  //Sの文字列からTの文字列があるか検索する
  bool contain(string S,string T){
    int left=0,right=S.length();
    while(right-left>1){
      int mid=(left+right)/2;
      if(S.compare(sa[mid],T.length(),T)<0)left=mid;
      else right=mid;
    }
    return S.compare(sa[right],T.length(),T)==0;
  }
  
  int compare(int a,int b,int n,RollingHash &A ,RollingHash &B,string &T){
    int L = 0, R = n;
    while(L+1<R){
      int M = (L+R)/2;
      if(a + M > (int)S.size() || A.get(a,a+M) != B.get(b,b+M)) R = M;
      else L = M;
    }

    if(L == n) return 1;
    if(S[a+L] < T[b+L]) return -1;
    return 1;
  }

  int Lower(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>=0) R = M;
      //if(S.compare(sa[M],T.size(),T)>=0) R = M;
      else L = M+1;
    }  
    return L;
  }
  
  int Upper(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>0) R = M;
      //if(S.compare(sa[M],T.size(),T)>0) R = M;
      else L = M+1;
    }
    
    return L;
  }

};

string s, p[100005];
SA sa = SA();

int Lower(string t){
  
  int l = 0, r = (int)s.size() + 1;
  
  while( l + 1 < r ){
    
    int m = ( l + r ) / 2;
    int idx = sa.sa[m];
    
    if( s.substr(idx) < t ) l = m;
    else r = m;
    
  }

  return r;
} // sa で　初めてt以上になるところのidx

typedef pair<int,int> P;

int n;

int main(){
  
  cin>>s;

  cin>>n;
  
  for(int i=0;i<n;i++) cin>>p[i];
  
  sort( p, p+n, [](const string &a,const string &b){
      return a.size() > b.size();
    });
  
  sa.construct_sa(s);
  
  int len = s.size();
  
  RMQ rmq = RMQ(len+1);
  
  for(int i=0;i<len+1;i++) rmq.update(i,i+1,0);
  
  for(int i=0;i<n;i++){
    
    string t = p[i];

    int L = Lower( t ), R = Lower( t + '{' );
    
    if( L == R || L >= len + 1 ) continue;
    
    rmq.update( Lower(t), Lower(t+'{'), (int)t.size() );
    
  }
  
  vector<P> v;
  
  for(int i=1;i<len+1;i++){
    
    v.push_back(P( rmq.find( i, i+1 ) + sa.sa[i] - 1 , sa.sa[i] ));
    
  }
  
  sort(v.begin(), v.end());
  
  int ans = 0, maxr = -1;
  
  for(int i=0;i<len;i++){
    
    int l = v[i].second, r = v[i].first;
    
    if( l > r ) continue;
    
    if( maxr < l ){
      ans++;
      maxr = r;
    }
    
  }
  
  cout<<ans<<endl;
  
  return 0;
}


```