#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i = 0; i < (int)(n); ++i) #define all(x) (x).begin(),(x).end() template void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } template inline bool chmax(T &a, T b){ if(a inline bool chmin(T &a, T b){ if(a>b){ a = b; return true; } return false; } class KMP { public: string pattern; int plen; vector table; KMP(const string& s) : pattern(s), plen((int)pattern.size()), table(plen + 1){ table[0] = -1; int j = -1; for(int i = 0; i < plen; ++i){ while(j >= 0 && pattern[i] != pattern[j]){ j = table[j]; } table[i+1] = ++j; } } void search(const string& text, vector& res){ int head = 0, j = 0, tlen = (int)text.size(); while(head + j < tlen){ if(pattern[j] == text[head + j]) { if(++j == plen){ res.push_back(head); head = head + j - table[j]; j = table[j]; } }else{ head = head + j - table[j]; if(j) j = table[j]; } } } }; // 文字列 s[0, i] の最小周期の長さ void minimum_cycle(const string& s, vector& res){ KMP kmp(s); res.resize((int)s.size()); for(int i = 0; i < (int)s.size(); ++i){ res[i] = i + 1 - kmp.table[i+1]; } } class suffixarray{ public: int sz,index1,index2; vector rnk,tmp,sa,lcp; string recs; suffixarray(string s){ recs = s; sz = (int)s.size(); rnk.resize(sz+1),tmp.resize(sz+1); make_sa(); // make_lcp(); } void make_sa(){ index1 = sz; sa.resize(index1+1); for(int i = 0; i < index1+1; i++){ sa[i] = i; rnk[i] = i 0){ h--; } for(;j+h> n >> m >> q; string s; cin >> s; if(m==1){ suffixarray sss(s); vector sa = sss.sa; rep(i,q){ int k; cin >> k; cout << sa[k]+1 << " "; } cout << endl; return 0; } vector res; minimum_cycle(s,res); ll c = res[n-1]; // cerr << c << endl; if(n%c!=0)c = n; ll loop = n*m/c; string t; rep(i,c){ t.push_back(s[i]); } s = t; s += s; suffixarray sss(s); vector sa = sss.sa; set st; set sst; vector > > a; for(int i=1;i<=s.size();i++){ if(sa[i]>=c){ a.push_back(MP(sa[i]%c,MP(1,1))); }else{ a.push_back(MP(sa[i]%c,MP(0,loop-1))); } } // for(auto x:a){ // cerr << x.first << " " << x.second.first << " " << x.second.second << endl; // } // cerr << c << " " << loop << endl; vector cnt; ll sm = 0; for(auto x:a){ cnt.push_back(sm); sm += x.second.second; } rep(i,q){ ll k; cin >> k; int id = lower_bound(all(cnt),k)-cnt.begin() -1; ll res = 0; ll D = k - cnt[id]; if(a[id].second.first){ res = c*(loop-1) + a[id].first; }else if(a[id].second.second==loop){ res = c*(loop-1) + a[id].first; res -= c*(D-1); }else{ res = c*(loop-2) + a[id].first; res -= c*(D-1); } cout << res+1 << " "; } cout << "\n"; return 0; }