#include using namespace std; #define int long long const int MOD = 1000000007; struct SuffixArray { string s; vector sa, rev; SuffixArray() {} SuffixArray(const string& S) : s(S) { int n = s.size(); s.push_back('$'); sa.resize(n + 1); iota(sa.begin(), sa.end(), 0); sort(sa.begin(), sa.end(), [&](int a, int b) { if (s[a] == s[b]) return a > b; return s[a] < s[b]; }); vector cs(n + 1, 0), rs(n + 1), cnt(n + 1); for (int i = 0; i <= n; i++) rs[i] = s[i]; for (int len = 1; len <= n; len *= 2) { for (int i = 0; i <= n; i++) { cs[sa[i]] = i; if (i > 0 && rs[sa[i - 1]] == rs[sa[i]] && sa[i - 1] + len <= n && rs[sa[i - 1] + len / 2] == rs[sa[i] + len / 2]) cs[sa[i]] = cs[sa[i - 1]]; } iota(cnt.begin(), cnt.end(), 0); copy(sa.begin(), sa.end(), rs.begin()); for (int i = 0; i <= n; i++) { int s1 = rs[i] - len; if (s1 >= 0) sa[cnt[cs[s1]]++] = s1; } cs.swap(rs); } rev.resize(n + 1); for (int i = 0; i <= n; i++) rev[sa[i]] = i; } int operator[](int i) const { return sa[i]; } bool lt_substr(string& t, int si, int ti) { int sn = s.size(), tn = t.size(); while (si < sn && ti < tn) { if (s[si] < t[ti]) return 1; if (s[si] > t[ti]) return 0; si++; ti++; } return si == sn && ti < tn; } int lower_bound(string& t) { int l = 0, r = s.size(); while (l + 1 < r) { int m = (l + r) >> 1; if (lt_substr(t, sa[m], 0)) l = m; else r = m; } return r; } int upper_bound(string& t) { t.back()++; int res = lower_bound(t); t.back()--; return res; } // O(|T|*log|S|) int count(string& T) { return upper_bound(T) - lower_bound(T); } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, Q; cin >> N >> M >> Q; string S; cin >> S; vector X(Q); for (int i = 0; i < Q; i++) { cin >> X[i]; } if (M == 1) { SuffixArray sa(S); for (int i = 0; i < Q; i++) { if (i > 0) cout << " "; cout << sa.sa[X[i]] + 1; } cout << endl; return 0; } vector res(Q); string T = S; S = S + S; SuffixArray sa(S); // for (int i = 0; i < sa.rev.size(); i++) { // cerr << sa.rev[i] << " "; // } // cerr << endl; int cnt = 0; vector v; int cur = 0; for (int i = 1; i < sa.sa.size(); i++) { if (sa.sa[i] < N) { v.push_back(sa.sa[i]); if (i + 1 == (int)sa.sa.size() || sa.sa[i + 1] > sa.sa[i]) { while (cur < Q) { int t = X[cur]; int rem = t - (i + cnt) + (int)v.size() - 1; if (rem < (M - 1) * v.size()) { int rep = rem / v.size(); res[cur] = v[rem % v.size()] + (M - 2 - rep) * N; //cerr << cur << " " << i << " " << v.size() << " " << v[0] << endl; cur++; } else { break; } } cnt += (M - 2) * v.size(); v.clear(); } } else { while (cur < Q) { if (i + cnt == X[cur]) { res[cur] = sa.sa[i] + (M - 2) * N; cur++; } else { break; } } } } assert(v.size() == 0); assert(cnt == (M - 2) * N); for (int i = 0; i < Q; i++) { if (i > 0) cout << " "; cout << res[i] + 1; } cout << endl; // S = ""; // for (int i = 0; i < M; i++) { // S += T; // } // SuffixArray sa2(S); // for (int i = 0; i < Q; i++) { // if (i > 0) cerr << " "; // cerr << sa2.sa[X[i]] + 1; // } // cerr << endl; return 0; }