#include using namespace std; #define int long long #define double long double #define FOR(i, a, b) for(ll i = (a); i < (b); ++i) #define FORR(i, a, b) for(ll i = (a); i > (b); --i) #define REP(i, n) for(ll i = 0; i < (n); ++i) #define REPR(i, n) for(ll i = n; i >= 0; i--) #define FOREACH(x, a) for(auto &(x) : (a)) #define VECCIN(x) \ for(auto &youso_ : (x)) cin >> youso_ #define bitcnt(x) __builtin_popcount(x) #define lbit(x) __builtin_ffsll(x) #define rbit(x) __builtin_clzll(x) #define SZ(x) ((ll)(x).size()) #define fi first #define se second #define All(a) (a).begin(), (a).end() #define rAll(a) (a).rbegin(), (a).rend() template inline T IN() { T x; cin >> x; return (x); } inline void CIN() {} template inline void CIN(Head &&head, Tail &&... tail) { cin >> head; CIN(move(tail)...); } #define CCIN(...) \ char __VA_ARGS__; \ CIN(__VA_ARGS__) #define DCIN(...) \ double __VA_ARGS__; \ CIN(__VA_ARGS__) #define LCIN(...) \ ll __VA_ARGS__; \ CIN(__VA_ARGS__) #define SCIN(...) \ string __VA_ARGS__; \ CIN(__VA_ARGS__) #define Yes(a) cout << (a ? "Yes" : "No") << "\n" #define YES(a) cout << (a ? "YES" : "NO") << "\n" #define Printv(v) \ { \ FOREACH(x, v) { cout << x << " "; } \ cout << "\n"; \ } template inline void eputs(T s) { cout << s << "\n"; exit(0); } template void Fill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); } template using PQG = priority_queue, greater>; template using PQ = priority_queue; typedef long long ll; typedef vector VL; typedef vector VVL; typedef pair PL; typedef vector VPL; typedef vector VB; typedef vector VD; typedef vector VS; const int INF = 1e9; const int MOD = 1e9 + 7; // const int MOD = 998244353; const ll LINF = 1e18; // const double PI = atan(1.0) * 4.0; const ll dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; const ll dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; #define PI 3.141592653589793238 // Sparse Table template struct SparseTable { vector> dat; vector height; SparseTable() {} SparseTable(const vector &vec) { init(vec); } void init(const vector &vec) { int n = (int)vec.size(), h = 0; while((1 << h) < n) ++h; dat.assign(h, vector(1 << h)); height.assign(n + 1, 0); for(int i = 2; i <= n; i++) height[i] = height[i >> 1] + 1; for(int i = 0; i < n; ++i) dat[0][i] = vec[i]; for(int i = 1; i < h; ++i) for(int j = 0; j < n; ++j) dat[i][j] = min(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]); } MeetSemiLattice get(int a, int b) { return min(dat[height[b - a]][a], dat[height[b - a]][b - (1 << height[b - a])]); } }; // NlogN struct SuffixArray { vector SA; string s; SuffixArray(const string &str) { Build_SA(str); } void Build_SA(const string &str) { s = str; SA.resize(s.size()); iota(begin(SA), end(SA), 0); sort(begin(SA), end(SA), [&](const int &a, const int &b) { if(s[a] == s[b]) return (a > b); return (s[a] < s[b]); }); vector classes(s.size()), c(s.size()), cnt(s.size()); for(int i = 0; i < s.size(); i++) { c[i] = s[i]; } 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); } SA.insert(SA.begin(), s.size()); } int operator[](int k) const { return (SA[k]); } int size() const { return (s.size()); } bool lt_substr(string &t, int si = 0, int ti = 0) { int sn = s.size(), tn = 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(string &t) { int low = -1, high = SA.size(); while(high - low > 1) { int mid = (low + high) >> 1; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } return (high); } pair lower_upper_bound(string &t) { int idx = lower_bound(t); int low = idx - 1, high = SA.size(); t.back()++; while(high - low > 1) { int mid = (low + high) >> 1; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } t.back()--; return (make_pair(idx, high)); } void output() { for(int i = 0; i < size(); i++) { cout << i << ": " << s.substr(SA[i]) << endl; } } }; struct LCP { vector lcp, rank; SparseTable st; LCP(SuffixArray &SA) { Build_LCP(SA); } int operator[](int k) const { return (lcp[k]); } int size() const { return (lcp.size()); } void Build_LCP(SuffixArray &SA) { string &s = SA.s; ll n = s.size(); rank.resize(n + 1); for(int i = 0; i <= n; ++i) rank[SA[i]] = i; lcp.resize(n + 1); lcp[0] = 0; int cur = 0; for(int i = 0; i < n; ++i) { int pi = SA[rank[i] - 1]; if(cur > 0) --cur; for(; pi + cur < n && i + cur < n; ++cur) { if(s[pi + cur] != s[i + cur]) break; } lcp[rank[i] - 1] = cur; } st.init(lcp); } // calc lcp int getLCP(int a, int b) { // lcp of str.sutstr(a) and str.substr(b) return st.get(min(rank[a], rank[b]), max(rank[a], rank[b])); } }; signed main() { LCIN(N); cin.tie(0); ios::sync_with_stdio(false); string s = ""; VL len(N), sum(N + 1); REP(i, N) { SCIN(S); len[i] = S.length(); s += S + (i == N - 1 ? "" : "$"); } REP(i, N) { sum[i + 1] += sum[i] + len[i] + 1; } // SuffixArray SA(s); // LCP lcp(SA); LCIN(M, x, d); ll ans = 0; REP(loop, M) { ll i = (x / (N - 1)) + 1, j = (x % (N - 1)) + 1; if(i > j) swap(i, j); else j++; x = (x + d) % (N * (N - 1)); i--, j--; } cout << ans << "\n"; }