class RMQ(object): def __init__(self, A): self._A = A self._preprocess() def _preprocess(self): n = len(self._A) max_j = n.bit_length() - 1 self._M = [list(range(n))] for j in range(0, max_j): shift = 1 << j Mj = self._M[j] Mjnext = [] for k1, k2 in zip(Mj, Mj[shift:]): k = k1 if self._A[k1] < self._A[k2] else k2 Mjnext.append(k) self._M.append(Mjnext) def query(self, i, j): if i == j: return self._A[i] el = (j - i).bit_length() - 1 Ak1 = self._A[self._M[el][i]] Ak2 = self._A[self._M[el][j - (1 << el) + 1]] if Ak1 < Ak2: return Ak1 else: return Ak2 class LCP(object): def __init__(self, strings): strings_with_index = [(s, i) for i, s in enumerate(strings)] strings_with_index.sort() sorted_strings = [] self._index_converter = [0] * len(strings) j = 0 for s, i in strings_with_index: sorted_strings.append(s) self._index_converter[i] = j j += 1 self._init_lcp_neighbours(sorted_strings) self._rmq = RMQ(self._lcp_neighbours) self._lens = list(map(len, sorted_strings)) def _init_lcp_neighbours(self, ss): n = len(ss) self._lcp_neighbours = [self._calc_lcp(ss[i], ss[i + 1]) for i in range(n - 1)] def _calc_lcp(self, str0, str1): lcp = 0 for c0, c1 in zip(str0, str1): if c0 != c1: return lcp else: lcp += 1 return lcp def get(self, i, j): ii = self._index_converter[i] jj = self._index_converter[j] if ii == jj: return self._lens[ii] elif ii > jj: return self._rmq.query(jj, ii - 1) else: return self._rmq.query(ii, jj - 1) if __name__ == '__main__': N = int(input()) strings = [input() for _ in range(N)] M, x, d = map(int, input().split()) lcp = LCP(strings) Nm1 = N - 1 NN = N * (N - 1) cum = 0 for k in range(M): i, j = divmod(x, Nm1) if (i > j): i, j = j, i else: j += 1 cum += lcp.get(i, j) x = (x + d) % NN print(cum)