import math class RMQ(object): def __init__(self, iterable): if len(iterable) <= 10**5: self._RMQ = RMQdoubling(iterable) else: self._RMQ = RMQfaster(iterable) def query(self, i, j): return self._RMQ.query(i, j) class RMQdoubling(RMQ): 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 RMQfaster(RMQdoubling): def __init__(self, D): self._D = D A, self._block_size = self._chop() super().__init__(A) def _chop(self): n = len(self._D) block_size = int(math.log2(n)/4) A = [min(self._D[i:i+block_size]) for i in range(0, n, block_size)] return A, block_size def _findmin(self, d_min, start, stop): for i, d in enumerate(self._D[start:stop], start): if d == d_min: return i def query(self, i, j): if i == j: return i if i > j: i, j = j, i s = self._block_size ii = (i - 1)//s + 1 jj = (j - 1)//s mid_block = super().query(ii, jj) d_mid = self._A[mid_block] d_min = d_mid for k in list(range(i, ii*s)) + list(range(jj*s, j+1)): if self._D[k] < d_min: d_min = self._D[k] k_min = k if d_min < d_mid: return k_min else: return self._findmin(d_min, mid_block*s, (mid_block+1)*s) 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] kk = self._rmq.query(ii, jj - 1) return self._lcp_neighbours[kk] if __name__ == '__main__': N = int(input()) strings = [input().rstrip() 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) i += 1 j += 1 if (i > j): i, j = j, i else: j += 1 cum += lcp.get(i - 1, j - 1) x = (x + d) % NN print(cum)