#include using namespace std; typedef long long ll; typedef pair l_l; typedef pair i_i; template inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } const long double EPS = 1e-10; const long long INF = 1e18; const long double PI = acos(-1.0L); //const ll mod = 1000000007; struct SuffixArray { vector< int > SA; const string s; SuffixArray(const string &str) : s(str) { SA.resize(s.size()); iota(begin(SA), end(SA), 0); sort(begin(SA), end(SA), [&](int a, int b) { return s[a] == s[b] ? a > b : s[a] < s[b]; }); vector< int > classes(s.size()), c(s.begin(), s.end()), cnt(s.size()); for(int len = 1; len < s.size(); len <<= 1) { for(int i = 0; i < s.size(); i++) { if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) { classes[SA[i]] = classes[SA[i - 1]]; } else { classes[SA[i]] = i; } } iota(begin(cnt), end(cnt), 0); copy(begin(SA), end(SA), begin(c)); for(int i = 0; i < s.size(); i++) { int s1 = c[i] - len; if(s1 >= 0) SA[cnt[classes[s1]]++] = s1; } classes.swap(c); } } int operator[](int k) const { return SA[k]; } size_t size() const { return s.size(); } bool lt_substr(const string &t, int si = 0, int ti = 0) { int sn = (int) s.size(), tn = (int) t.size(); while(si < sn && ti < tn) { if(s[si] < t[ti]) return true; if(s[si] > t[ti]) return false; ++si, ++ti; } return si >= sn && ti < tn; } int lower_bound(const string &t) { int low = -1, high = (int) SA.size(); while(high - low > 1) { int mid = (low + high) / 2; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } return high; } pair< int, int > lower_upper_bound(string &t) { int idx = lower_bound(t); int low = idx - 1, high = (int) SA.size(); t.back()++; while(high - low > 1) { int mid = (low + high) / 2; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } t.back()--; return {idx, high}; } void output() { for(int i = 0; i < size(); i++) { cout << i << ": " << s.substr(SA[i]) << endl; } } }; struct LongestCommonPrefixArray { const SuffixArray &SA; vector< int > LCP, rank; LongestCommonPrefixArray(const SuffixArray &SA) : SA(SA), LCP(SA.size()) { rank.resize(SA.size()); for(int i = 0; i < SA.size(); i++) { rank[SA[i]] = i; } for(int i = 0, h = 0; i < SA.size(); i++) { if(rank[i] + 1 < SA.size()) { for(int j = SA[rank[i] + 1]; max(i, j) + h < SA.size() && SA.s[i + h] == SA.s[j + h]; ++h); LCP[rank[i] + 1] = h; if(h > 0) --h; } } } int operator[](int k) const { return LCP[k]; } size_t size() const { return LCP.size(); } void output() { for(int i = 0; i < size(); i++) { cout << i << ": " << LCP[i] << " " << SA.s.substr(SA[i]) << endl; } } }; bool AllSame(string S) { sort(S.begin(), S.end()); return S[0] == S.back(); } map mp; ll ans[100050]; int main() { //cout.precision(10); cin.tie(0); ios::sync_with_stdio(false); ll N, M, Q; cin >> N >> M >> Q; string S; cin >> S; if(AllSame(S)) { for(int q = 0; q < Q; q++) { if(q != 0) cout << " "; ll K; cin >> K; cout << N * M - K + 1; } cout << endl; return 0; } S = S + S + S; SuffixArray SA(S); for(int i = 0; i < S.size(); i++) { cerr << SA[i] << " "; } cerr << endl; ll nowone = 0; ll nowrep = 0; vector Query(Q); for(int i = 0; i < Q; i++) { Query[i].second = i; cin >> Query[i].first; Query[i].first--; } sort(Query.begin(), Query.end()); ll nownum = 0; ll idx = 0; for(int i = 0; i < S.size(); i++) { if(SA[i] < 2 * N) { //mp[SA[i]-N] = {nowrep, nowone}; ll delta = SA[i] - SA[i+1]; ll tmp = SA[i] - N + N * (M - 2); ll tmpnum = tmp / delta + 1; cerr << "main: " << i << " " << tmp << " " << idx << " " << delta << " " << tmpnum << endl; assert(SA[i] >= N); while(idx < Q and nownum + tmpnum - 1 >= Query[idx].first) { //cerr << idx << " " << i << endl; ll tmp = SA[i] - N; tmp += N * (M - 2); //cerr << idx << " " << tmp << endl; tmp -= (Query[idx].first - nownum) * delta; //cerr << idx << " " << tmp << endl; ans[Query[idx].second] = tmp; idx++; } nowrep++; nownum += tmpnum; i += SA[i] / delta + 1 - 1; } else { //mp[SA[i]] = {nowrep, nowone}; //cerr << "sub:" << i << " " << nownum << endl; if(idx < Q and Query[idx].first == nownum) { ll tmp = SA[i] + N * (M - 3); ans[Query[idx].second] = tmp; idx++; } nowone++; nownum++; } } for(int i = 0; i < Q; i++) { if(i != 0) cout << " "; cout << ans[i] + 1; } cout << endl; return 0; }