#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define X first #define Y second #define pb push_back #define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X)) #define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X)) #define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X)) #define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X)) #define repe(X,Y) for ((X) = 0;(X) < (Y);++(X)) #define peat(X,Y) for (;(X) < (Y);++(X)) #define all(X) (X).begin(),(X).end() #define rall(X) (X).rbegin(),(X).rend() #define eb emplace_back #define UNIQUE(X) (X).erase(unique(all(X)),(X).end()) #define Endl endl #define NL <<"\n" using namespace std; using ll=long long; using pii=pair; using pll=pair; template using vv=vector>; template inline bool MX(T &l,const T &r){return l inline bool MN(T &l,const T &r){return l>r?l=r,1:0;} //#undef NUIP #ifdef NUIP #include "benri.h" #else #define out(args...) #endif #ifdef __cpp_init_captures templatevector table(int n, T v){ return vector(n, v);} template auto table(int n, Args... args){auto val = table(args...); return vector(n, move(val));} #endif const ll MOD=1e9+7; //998244353 struct RMQ{ const int INF=MOD; vv mn; int D; void upd(const vector &v){ mn.clear(); D=0; for(int i=v.size();i;i/=2) ++D; mn.resize(D+1,vector(1<>(D-i)|1)<<(D-i); //assert(b!=(1<>(D-i)&1)); mn[i][j]=j>>(D-i)&1?get(b,j+1):get(j,b); } } RMQ(){} RMQ(const vector &v){upd(v);} int get(int l,int r){ //[l,r) --r; if(l==r)return mn[D][l]; if(l>r) return INF; int d=__builtin_clz(l^r)+D-31; return min(mn[d][l],mn[d][r]); } }; // Larsson-Sadakane's Suffix array Construction: O(n (log n)^2) struct SA:public vector{ struct SAComp { const int h; const vector &g; SAComp(int h, const vector &g) : h(h), g(g) {} bool operator() (int a, int b) { return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h]; } }; vector inv,lcp; string str; RMQ rmq; SA(){} SA(const string &str):str(str){build(str);} void build(const string &s){ str=s; buildSA(); buildLCP(); rmq.upd(lcp); inv.resize(size()); rep(i,size()) inv[at(i)]=i; } void buildSA(){ int n=str.size(); vector g(n+1),b(n+1); resize(n+1); rep(i,n+1) at(i)=i, g[i]=str[i]; sort(all(*this), SAComp(0,g)); for(int h=1; b[n]!=n; h*=2) { SAComp comp(h,g); sort(all(*this),comp); rep(i,n) b[i+1]=b[i]+comp(at(i),at(i+1)); rep(i,n+1) g[at(i)]=b[i]; } } void buildLCP(){ int n=str.size(); int h=0; vector b(n+1); lcp.resize(n+1); rep(i,n+1) b[at(i)]=i; rep(i,n+1) { if(b[i]){ for (int j=at(b[i]-1); j+h0) --h; } } int getMn(int l,int r){return rmq.get(l+1,r+1);} }; ostream& operator<<(ostream &os,const SA &sa){ rep(i,sa.size()) os< &re){ re.resize(str.size()+1); re[0]=-1; int j=-1; rep(i,str.size()){ while(j>=0 && str[i]!=str[j]) j=re[j]; re[i+1]=++j; } } vector solve(string s,ll m,vector inds){ const int q=inds.size(); const int n=s.size(); if(m==1){ SA sa(s); vector re(q); rep(i,q) re[i]=sa[inds[i]+1]; return re; } SA sa(s+s); out(sa,1); vector ps; ll cur=0; for(auto x:sa){ if(x==2*n) continue; ps.eb(cur,x); if(x re(q); ll ad=(m-2ll)*n; rep(i,q){ auto ind=inds[i]; auto p=*(upper_bound(all(ps),pll(ind+1,-10))-1); out(p,1); auto dif=ind-p.X; re[i]=p.Y+ad-n*dif; } return re; } vector naive(string s,ll m,vector inds){ string ss; rep(_,m) ss+=s; return solve(ss,1,inds); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout< inds(n*m); iota(all(inds),0); auto exp=naive(s,m,inds); auto act=naive(s,m,inds); if(exp!=act){ out(s,m,inds,exp,act,1); return 0; } } return 0; } ll n,m,q; cin>>n>>m>>q; string s; cin>>s; vector inds(q); for(auto &x:inds) cin>>x, --x; vector kmp; ::kmp(s,kmp); out(kmp,1); if(kmp.back() && n%kmp.back()==0){ s=s.substr(0,n-kmp.back()); m*=n/kmp.back(); } auto re=solve(s,m,inds); rep(i,q) cout<