折半爆搜，首先爆搜出所有长度不超过$4$的串。
对于每个询问，首先暴力枚举所有长度不超过$4$的串，以及前$4$位相同时后面的串。
然后枚举前$4$位，以及后面的串长，那么后面的hash值唯一，可以双指针求出。
时间复杂度$O(26^4(log(26^4)+k))$。
#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;
}