#include #include #include constexpr int N = 800001; char buf[N]; int trie[N][26]; int pos[100000]; bool marked[N]; int eulerID[N]; int now; int rmq[22][N * 2]; int lg[N * 2]; int readint() { int n; scanf("%d", &n); return n; } long long readlong() { long long n; scanf("%lld", &n); return n; } void dfs(int u, int depth) { eulerID[u] = now; rmq[0][now++] = depth; for (int i = 0; i < 26; i++) { if (!trie[u][i]) { continue; } dfs(trie[u][i], depth + 1); rmq[0][now++] = depth; } } int main() { clock_t beg, end; beg = clock(); const int n = readint(); int cnt = 1; for (int i = 0; i < n; i++) { scanf("%s", buf); int u = 0; for (int j = 0; buf[j] != 0; j++) { char c = buf[j] - 'a'; if (!trie[u][c]) { trie[u][c] = cnt++; } u = trie[u][c]; } pos[i] = u; } dfs(0, 0); for (int i = 2; i < N * 2; i++) { lg[i] = lg[i / 2] + 1; } for (int i = 0; i < 21; i++) { for (int j = 0; j + (1 << i) < N * 2; j++) { rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]); } } end = clock(); fprintf(stderr, "%.20f\n", (double)(end - beg) / CLOCKS_PER_SEC); const int m = readint(); const long long x = readlong(); const long long d = readlong(); int ii = x % (n - 1); int jj = x / (n - 1); const int di = d % (n - 1); const int dj = d / (n - 1); long long ans = 0; for (int foo = 0; foo < m; foo++) { int i = jj; int j = ii; if (i > j) { std::swap(i, j); } else { j++; } ii += di; if (ii >= n - 1) { ii -= n - 1; jj++; } jj += dj; if (jj >= n) { jj -= n; } int l = eulerID[pos[i]]; int r = eulerID[pos[j]] + 1; if (l > r) { std::swap(l, r); } const int k = lg[r - l]; ans += std::min(rmq[k][l], rmq[k][r - (1 << k)]); } printf("%lld\n", ans); end = clock(); fprintf(stderr, "%.20f\n", (double)(end - beg) / CLOCKS_PER_SEC); }