import math class RMQ(object): def __init__(self, A): self._A = A self._preprocess() def _preprocess(self): ''' RMQ の前処理。 ''' n = len(self._A) max_j = int(math.log2(n)) 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 i if i > j: i, j = j, i el = int(math.log2(j - i)) k1 = self._M[el][i] k2 = self._M[el][j - (1 << el) + 1] rmq = k1 if self._A[k1] < self._A[k2] else k2 return rmq class LCP(object): '''Longest Common Prefix を計算するクラス lcp = LCP(lst_of_strings) lcp.get(i, j) ''' 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): ''' strings[i] と strings[j] の LCP の長さを返す ''' ii = self._index_converter[i] jj = self._index_converter[j] if ii == jj: return self._lens[ii] if ii > jj: ii, jj = jj, ii kk = self._rmq.query(ii, jj - 1) return self._lcp_neighbours[kk] 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)