#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long ll;

typedef unsigned int U;

const int N=460000;

const ll inf=1LL<<60;

int seed,L,Q,ansl,sl;U H,mul[4];ll ans,ss,po[8];

struct P{U h;int s;P(){}P(U _h,int _s){h=_h,s=_s;}};

inline bool cmpa(const P&x,const P&y){return x.h<y.h;}

inline bool cmpb(const P&x,const P&y){return x.h==y.h?x.s<y.s:x.h<y.h;}

struct DS{

int n;P a[N];

void add(P t){a[++n]=t;}

void inita(){std::sort(a+1,a+n+1,cmpa);}

void initb(){

  std::sort(a+1,a+n+1,cmpb);

  int m=0;

  for(int i=1;i<=n;i++)if(i==1||a[i].h!=a[i-1].h)a[++m]=a[i];

  n=m;

}

}A[5],B[5],C[5];

void dfs(int l,U h,int s){

  if(l)B[l].add(P(h,s)),C[l].add(P(h,s));

  if(l==4){

    for(int i=1;i<=4;i++)A[i].add(P(h*=seed,s));

    return;

  }

  for(int i=0;i<26;i++)dfs(l+1,h*seed+i+'A',s+po[3-l]*i);

}

inline void up(ll x,int y){

  if(x==ss&&y==sl)return;

  if(x>ans)return;

  if(x<ans||x==ans&&y<ansl)ans=x,ansl=y;

}

void solve(){

  char s[100];

  scanf("%s",s);

  int n=strlen(s),i,j,k;

  sl=n;

  for(i=H=ss=0;i<n;i++)H=H*seed+s[i],ss+=po[7-i]*(s[i]-'A');

  ans=inf;

  for(i=1;i<=4&&i<=L;i++)for(j=1;j<=C[i].n;j++)if(C[i].a[j].h==H)up(1LL*po[4]*C[i].a[j].s,i);

  if(sl>4&&sl<=L){

    U tmp=0;ll t=0;

    for(i=0;i<4;i++)tmp=tmp*seed+s[i],t+=po[7-i]*(s[i]-'A');

    tmp*=mul[sl-4];

    for(j=1;j<=C[sl-4].n;j++)if(tmp+C[sl-4].a[j].h==H)up(t+C[sl-4].a[j].s,sl);

  }

  for(i=1;i<=4&&i+4<=L;i++){

    U o=~0U;

    for(j=1,k=B[i].n;j<=A[i].n;j++){

      U t=H-A[i].a[j].h;

      if(t>o)k=B[i].n;

      o=t;

      while(k&&B[i].a[k].h>t)k--;

      if(k&&B[i].a[k].h==t)up(1LL*po[4]*A[i].a[j].s+B[i].a[k].s,i+4);

    }

  }

  if(ans==inf)puts("-1");

  else{

    for(i=0;i<ansl;i++)putchar(ans/po[7-i]%26+'A');

    puts("");

  }

}

int main(){

  scanf("%d%d%d",&seed,&L,&Q);

  for(int i=mul[0]=1;i<4;i++)mul[i]=mul[i-1]*seed;

  for(int i=po[0]=1;i<8;i++)po[i]=po[i-1]*26;

  dfs(0,0,0);

  for(int i=1;i<=4;i++)A[i].inita(),B[i].initb();

  while(Q--)solve();

  return 0;

}