#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <assert.h>

using namespace std;

class MorphEncap{
public:
  size_t minim;
  vector<string> morph;
  MorphEncap *firstmorph;
  vector<string> Sh;
  vector<map<string, vector<pair<string, int> > > > factors;
  map<string, string> preimages;
  vector<pair<string,string> > borders;
  size_t computedUntil;
  
  MorphEncap(vector<string>& m):morph(m),firstmorph(this),factors(5000){
    minim =10000;
    for(size_t i=0; i<m.size(); i++) if(minim>m[i].size()) minim=m[i].size();
    initfact(6);
    initSh();
    initBorders();
    preimages[""]="";
  }
  
  MorphEncap(vector<string>& m, MorphEncap* m1):morph(m),firstmorph(m1),factors(5000){
    minim =10000;
    for(size_t i=0;i<m.size();i++) if(minim>m[i].size()) minim=m[i].size();
    computedUntil=0;
    initSh();
    initBorders();
    preimages[""]="";
  }
  
  friend ostream& operator<<(ostream& out, const MorphEncap& m){
    for(size_t i=0;i<m.morph.size();i++) cout<<(char)('0'+i)<< " -> "<< m.morph[i]<<endl;
    return out;
  }
  void image(const string & in, string & out)const {
    for(size_t i=0;i<in.size();i++)
      out += morph[in[i]-'0'];
  }
  void initfact(size_t n){
    factors[0][""].push_back(pair<string,int>("",0));
    cout<<"****************"<<endl<<"Initializing factors of :"<<endl<<(*this)<<endl;
    string s("a");
    for(size_t i=0;i<morph.size();i++){
      for(size_t j=0;j<morph[i].size();j++)
        for(size_t k=1;k<=morph[i].size()-j;k++)
          factors[k][morph[i].substr(j,k)].push_back(pair<string,int>(s,j));
      s[0]++;
    }
    for(auto it=factors[1].begin(),ie=factors[1].end(); it!=ie; it++){
        string res;
        image(it->first,res);
        if(preimages.find(res) == preimages.end()) preimages[res] = it->first;
        else{cout<< "The morphism is not injective!!!"<<endl<<"Stoping!!"<<endl;assert(0);}
    }
    computedUntil=n;
    for(size_t i=2; i<=computedUntil;i++){
      vector<string> listtemp;
      cout<<"computing from factors of size "<<i<<" which are :"<<endl;
      for(auto it=factors[i].begin(), ie = factors[i].end();it!=ie;it++)
        listtemp.push_back(it->first);
      size_t ll=0;
      while(ll < listtemp.size()){
        string res;
        image(listtemp[ll],res);
        cout<<listtemp[ll]<<" image is "<<res<<endl;
        for(size_t j=0;j<morph[listtemp[ll][0]-'0'].size();j++)
          for(size_t k=res.size()-j-morph[listtemp[ll][listtemp[ll].size()-1]-'0'].size()+1;k<=res.size()-j;k++){
            factors[k][res.substr(j,k)].push_back(pair<string,int>(listtemp[ll],j));
            if(k==i && factors[k][res.substr(j,k)].size()==1) listtemp.push_back(res.substr(j,k));
          }
        ll++;
      }
      for(auto it=factors[i].begin(),ie=factors[i].end(); it!=ie; it++){
        string res;
        image(it->first,res);
        if(preimages.find(res) == preimages.end()) preimages[res] = it->first;
        else{cout<< "The morphism is not injective!!!"<<endl<<"Stoping!!"<<endl;assert(0);}
      }
    }
  }
  void increasecomp(int l){
    for(int i=computedUntil+1; i<=l;i++){
      if(firstmorph!= this) firstmorph->increasecomp(i);
      for(auto it = firstmorph->factors[i].begin(),ie = firstmorph->factors[i].end(); it!=ie; it++){
        string res;
        image(it->first, res);
        for(size_t j=0;j<morph[it->first[0]-'0'].size();j++)
          for(size_t k= max((int)(res.size()-j-morph[it->first[it->first.size()-1]-'0'].size()+1),0);k<=res.size()-j;k++)
            factors[k][res.substr(j,k)].push_back(pair<string,int>(it->first,j));
      }
      for(auto it = firstmorph->factors[i].begin(),ie = firstmorph->factors[i].end();it!=ie;it++){
        string res;
        image(it->first,res);
        if(preimages.find(res) == preimages.end()) preimages[res] = it->first;
        else{cout<< "The morphism is not injective!!!"<<endl<<"Stoping!!"<<endl;assert(0);}
      }
      computedUntil=i;
    }
  }
  void initSh(){
    cout<<endl<<"****************"<<endl<<"Computing Sh of :"<<endl<<(*this)<<endl;
    bool done= false;
    int i=1;
    while(!done){
      done = true;
      increasecomp(i/minim+4);
      //increasecomp(i);
      for(auto it = factors[i].begin(), ie = factors[i].end();it != ie;it++){
        vector<size_t> synch(i+1,0);
        for(size_t j=0;j<it->second.size();j++){
          int v=-(it->second[j].second);
          for(size_t k=0;k<it->second[j].first.size();k++){
            if (v>=0 && v<=i) synch[v]++;
            v+= morph[it->second[j].first[k]-'0'].size();
          }
          if (v>=0 && v<=i) synch[v]++;
        }
        int synchpoint=0;
        for(int j=0; j<i+1; j++) if(synch[j]==it->second.size()) synchpoint++;
        if(synchpoint<2){
          done = false;
          Sh.push_back(it->first);
           cout<<it->first<<" ";
        }
      }
      i++;
      if(i>1000){ 
        cout<<"The morphisme is not circular (or for i >1000?)"<<endl;
        assert(0);
        break;
        
      }
    }
    cout<<"Size of Sh is "<<Sh.size()<<endl<<endl;
  }
  void initBorders(){
    set<string> beg, end;
    beg.insert("");
    end.insert("");
    for(size_t i=0;i<morph.size();i++)
      for(size_t j=1;j<morph[i].size();j++){
        beg.insert(morph[i].substr(0,j));
        end.insert(morph[i].substr(j));
      }
    for(auto it = beg.begin(),ie = beg.end();it!=ie;it++)
      for(auto eit = end.begin(),eie = end.end();eit!=eie;eit++){
        borders.push_back(pair<string,string>(*it,*eit));
      }
     for(size_t i=0; i<borders.size();i++) cout << borders[i].first<< " "<<borders[i].second<<" || ";
     cout<<endl;
    cout<<"Size of border is "<<borders.size()<<endl<<endl;
  }
  bool setpreim(string & s){
    increasecomp(s.size()/minim+4);
    if(preimages.find(s) == preimages.end()) return false;
    else{
      s = preimages[s]; 
      return true;
    }
  }
  bool isafactor(const string & s){
    increasecomp(s.size()/minim+4);
    if(factors[s.size()].find(s) == factors[s.size()].end()) return false;
    else return true;
  }
};

class Patern{
public:
  vector<string> c;
  string pat;

  Patern(const string& pat, int par= -1) :  c(pat.size()+1,""), pat(pat){
  }
  Patern(const Patern & P) : c(P.c), pat(P.pat){
  }
  string getpat()const{
    string s;   
    for(size_t i=0; i<pat.size(); i++)  s += c[i]+pat[i];
    s += c[pat.size()];
    return s;
  }
  friend ostream& operator<<(ostream& out, const Patern& p){
    out<< p.getpat();
    return out;
  }
  inline bool operator < (const Patern &P) const{
    if(pat< P.pat) return true;
    if(pat> P.pat) return false;
    if(c.size()<P.c.size()) return true;
    if(c.size()>P.c.size()) return false;
    for(size_t i =0; i<c.size(); i++){
      if(c[i] < P.c[i]) return true;
      if(c[i] > P.c[i]) return false; 
    }
    return false;
  } 
  inline bool operator == (const Patern &P) const{
    if(pat != P.pat) return false;
    if(c.size()!=P.c.size()) return false;
    for(size_t i =0; i<c.size(); i++)
      if(c[i] != P.c[i]) return false;  
    return true;
  }
};

void recReplace(const Patern& P, Patern & NP, int nextVar, vector<int>& replacedby, MorphEncap& morph, set<Patern>& seen, vector<Patern>& list, bool secondmorph){
  if(nextVar == P.pat.size()){
    if(NP.pat.back()=='.'){
      char tc= NP.pat.back();
      string temp= NP.c.back();
      NP.pat.pop_back();
      NP.c.pop_back();
      if(secondmorph || seen.insert(NP).second)
        list.push_back(NP);
      NP.pat+=tc;
      NP.c.push_back(temp);
    }else{
      if(secondmorph || seen.insert(NP).second)
        list.push_back(NP);
    }
  }else{
    if(P.pat[nextVar] == '.'){
      if(NP.pat.size()!=0 && NP.pat.back()!='.'){
        NP.pat += '.';
        NP.c.push_back(P.c[nextVar+1]);
        recReplace(P, NP, nextVar+1, replacedby, morph, seen, list, secondmorph);
        NP.pat.pop_back();
        NP.c.pop_back();
      }else{
        string temp = NP.c.back();
        NP.c.back() = P.c[nextVar+1];
        recReplace(P, NP, nextVar+1, replacedby, morph, seen, list, secondmorph);
        NP.c.back() = temp;
      }
    }else if(replacedby[P.pat[nextVar]-'A'] == -2){
      for(replacedby[P.pat[nextVar]-'A']= -1; replacedby[P.pat[nextVar]-'A']<(int)(morph.Sh.size()); replacedby[P.pat[nextVar]-'A']++){
        recReplace(P, NP, nextVar, replacedby, morph, seen,  list, secondmorph);
      }
      replacedby[P.pat[nextVar]-'A']=-2;
    }else if(replacedby[P.pat[nextVar]-'A'] == -1){
      NP.pat+=P.pat[nextVar];
      NP.c.push_back(P.c[nextVar+1]);
      recReplace(P, NP, nextVar+1, replacedby, morph, seen,  list, secondmorph);
      NP.pat.pop_back();
      NP.c.pop_back();
    }else{
      string temp = NP.c.back();
      NP.c.back() += morph.Sh[replacedby[P.pat[nextVar]-'A']]+ P.c[nextVar+1];
      if(NP.c.back().size() == 0 || morph.isafactor(NP.c.back()))
        recReplace(P, NP, nextVar+1, replacedby, morph, seen,  list, secondmorph);
      NP.c.back()=temp;
    }
  }
}

void replace(const Patern & P, MorphEncap& morph, set<Patern>& seen, vector<Patern>& list, int nbVars, bool secondmorph){
  Patern NP("");
  vector<int> replacedby(nbVars,-2);
  NP.c[0]=P.c[0];
  recReplace(P, NP, 0, replacedby, morph, seen, list, secondmorph);
}


void recfind(const Patern& P, Patern& NP, vector<int>& select, int nextVar, const string &fromLeft, MorphEncap& morph, set<Patern>& seen, vector<Patern>& list, const Patern& todiv){
  if(nextVar == P.pat.size()){    
    for(size_t i=0; i<morph.borders.size(); i++){
      NP.c[nextVar] = fromLeft; 
      NP.c[nextVar] += P.c[nextVar]; 
      NP.c[nextVar] += morph.borders[i].second; 
      if(morph.setpreim(NP.c[P.pat.size()])){
        if(seen.insert(NP).second){
            list.push_back(NP);
        }
      }
    }
  }else{
    if(P.pat[nextVar] == '.'){
      for(size_t i=0; i<morph.borders.size(); i++){
        NP.c[nextVar] = fromLeft; 
        NP.c[nextVar] += P.c[nextVar]; 
        NP.c[nextVar] += morph.borders[i].second; 
        if(morph.setpreim(NP.c[nextVar]))
           recfind(P, NP, select, nextVar+1, morph.borders[i].first, morph, seen, list, todiv);
      }
    }else if(select[P.pat[nextVar]-'A'] == -1){
      for(select[P.pat[nextVar]-'A']=0; (size_t)select[P.pat[nextVar]-'A']<morph.borders.size(); select[P.pat[nextVar]-'A']++)
        recfind(P, NP, select, nextVar, fromLeft, morph, seen, list, todiv);
      select[P.pat[nextVar]-'A']=-1;
    }else{
        NP.c[nextVar] = fromLeft; 
        NP.c[nextVar] += P.c[nextVar]; 
        NP.c[nextVar] += morph.borders[select[P.pat[nextVar]-'A']].second; 
        if(morph.setpreim(NP.c[nextVar]))
           recfind(P, NP, select, nextVar+1,  morph.borders[select[P.pat[nextVar]-'A']].first, morph, seen, list, todiv);      
    }
  }
}


int done=0, lefttodo=0;
bool recancestors(const Patern &P,  MorphEncap&morph, set<Patern>& seen, int nbVars){
  vector<Patern> todo(1, P);
  replace(P, morph, seen, todo, nbVars,false); 
  vector<Patern> list;
  for(size_t i=0; i<todo.size(); i++){
    if(todo[i].pat.size()==0){cout<<"The factor "<<todo[i].c[0]<<" should be forbidden"<<endl; return false;}
    vector<int> select(nbVars, -1);
    Patern NP(todo[i].pat, 0);
    for(size_t fl =0; fl<morph.borders.size(); fl++)
      recfind(todo[i], NP, select, 0, morph.borders[fl].first, morph, seen, list, P);
  }
  lefttodo += list.size();
  for(size_t i=0;i<list.size();i++) 
    if(!recancestors(list[i], morph, seen, nbVars)){cout <<"---> "<<P<<endl; return false;}
  done++;
  if(done%10000==0)
    cout<< done<< " done out of "<<lefttodo<<endl;
  return true;
}

bool findancestors(const Patern &P, MorphEncap& morph2, MorphEncap& morph, set<Patern>& seen, int nbVars){
  vector<Patern> todo(1, P);
  replace(P, morph2, seen, todo, nbVars, true); 
      vector<Patern> list;
  for(size_t i=0; i<todo.size(); i++){
    if(todo[i].pat.size()==0) return false;
    vector<int> select(nbVars, -1);
    Patern NP(todo[i].pat, 0);
    for(size_t fl =0; fl<morph2.borders.size(); fl++)
      recfind(todo[i], NP, select, 0, morph2.borders[fl].first, morph2, seen, list, Patern("AAAAAAAAA"));
  }
  lefttodo += list.size();
  for(size_t i=0;i<list.size();i++) 
    if(!recancestors(list[i], morph, seen, nbVars)) return false;
  done++;
  return true;
}

int normalize(string& s){// normalise les formules
  vector<int> sentto(26,-1);
  int nbVars = 0;
  for(size_t i=0; i<s.size(); i++)
    if(s[i]!='.' && sentto[s[i]-'A'] == -1) sentto[s[i]-'A'] = nbVars++;
  for(size_t i=0;i<s.size();i++)
    if(s[i]!='.') s[i] = sentto[s[i]-'A']+'A';
  return nbVars;// renvoie le nombre total de lettre du pattern normalisé
}

int main(){
  //reading inputs
  string formula;
  cin >> formula;
  int nbVars = normalize(formula);
  Patern P(formula);
  
  int sizeA;
  cin >> sizeA;
  vector<string> m(sizeA);
  for(int i=0; i<sizeA; i++) cin>>m[i];
  MorphEncap morph(m);  
  vector<string> m2(sizeA);
  for(int i=0; i<sizeA; i++) cin>>m2[i];
  MorphEncap morph2(m2, &morph);
  
  set<Patern> seen;
  if(findancestors(P, morph2, morph, seen, nbVars)) cout<< "The formula "<<formula<< " is avoided by the morphism !!!!!!!!!!!!!!!!!!"<<endl<< "The set of patterns is of size "<<seen.size()<<endl;
  else cout<< "The formula "<<formula<< "  is NOT avoided!!"<<endl;
  return 0;
}