#include using namespace std; using lint = long long int; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector &vec, int len) { vec.resize(len); } template void ndarray(vector &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); } template bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } template istream &operator>>(istream &is, vector &vec){ for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const deque &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; // Suffix Array / Longest Common Prefix Array Construction // Comlexity: O(N(log N)^2) template struct SuffixArray { T S; // size: N std::vector SA; // Suffix Array (size: N + 1, SA[0] == N) SA[i] means S[SA[i]:] std::vector rank; // Rank (inverse of SA) (size: N + 1, rank[N] == 0) std::vector lcp; // Longest Common Prefix Array (size: N) betw. S[SA[i]:] & S[SA[i + 1]:] SuffixArray(const T &str, bool gen_lcp = true) : S(str) { int N = S.size(); SA.resize(N + 1); std::iota(SA.begin(), SA.end(), 0); rank.assign(N + 1, -1); for (int i = 0; i < N; i++) rank[i] = S[i]; int _ord_mm = 1; auto _comp_suffarr = [&](int i, int j) { if (rank[i] != rank[j]) return rank[i] < rank[j]; int ri = i + _ord_mm < (int)rank.size() ? rank[i + _ord_mm] : -1; int rj = j + _ord_mm < (int)rank.size() ? rank[j + _ord_mm] : -1; return ri < rj; }; std::vector tmp(N + 1); for (_ord_mm = 1; _ord_mm <= N; _ord_mm *= 2) { std::sort(SA.begin(), SA.end(), _comp_suffarr); tmp[SA[0]] = 0; for (int i = 1; i <= N; i++) { tmp[SA[i]] = tmp[SA[i - 1]] + _comp_suffarr(SA[i - 1], SA[i]); } rank = tmp; } if (!gen_lcp) return; lcp.assign(N, 0); int h = 0; for (int i = 0; i < N; i++) { int j = SA[rank[i] - 1]; if (h) h--; for (; j + h < N and i + h < N; h++) if (S[j + h] != S[i + h]) break; lcp[rank[i] - 1] = h; } } }; // Z algorithm (length of longest common prefix for s[0:N] & s[i:N] for each i) // Complexity: O(N) // vector z_algorithm(const string &s) { vector ans(s.size()); ans[0] = s.size(); int i = 1, j = 0; while (i < (int)s.size()) { while (i + j < (int)s.size() && s[j] == s[i + j]) ++j; ans[i] = j; if (!j) { ++i; continue; } int k = 1; while (i + k < (int)s.size() && k + ans[k] < j) ans[i + k] = ans[k], ++k; i += k; j -= k; } return ans; } int main() { lint N, M, Q; cin >> N >> M >> Q; string S; cin >> S; if (M < 5) { string T; REP(_, M) T += S; SuffixArray s(T, false); while (Q--) { int k; cin >> k; printf("%d ", s.SA[k] + 1); } puts(""); return 0; } auto z = z_algorithm(S); int rec = S.length(); REP(i, N) if (i and z[i] + i == N and N % i == 0) chmin(rec, i); // if (S == string(N, S[0])) { // while (Q--) { // lint K; // cin >> K; // printf("%lld ", N * M + 1 - K); // } // puts(""); // } S = S.substr(0, rec); M = M * (N / rec); N = rec; string S3 = S + S + S; SuffixArray sa3(S3, false); SuffixArray sa4(S3 + S, false); vector rnkM(N * 3); REP(i, N * 3) rnkM[i] = sa3.rank[i] + 1LL * (sa4.rank[i + N] - sa3.rank[i]) * (M - 3); map mp; REP(i, N * 3) mp[rnkM[i]] = N * (M - 3) + i; map val2pos; REP(i, N) val2pos[rnkM[i]] = i; while (Q--) { lint k; cin >> k; if (mp.count(k)) printf("%lld ", mp[k]); else { lint i = prev(val2pos.upper_bound(k))->second; lint d = k - rnkM[i]; printf("%lld ", i + 1 + N * (M - 3 - d)); } } }