Problem Statement

There is an array of strings $s_1,\cdots,s_N$. Answer $M$ queries of the following form:
"For integers $i,j$ satisfying $1\le i < j \le N$, find the length of the longest common prefix of the strings $s_i,s_j$."
The $M$ queries are generated from the seeds x,d by the following method. Read it carefully and implement it.

for k in 1 .. M
  i[k] = (x / (n - 1)) + 1
  j[k] = (x % (n - 1)) + 1
  if (i[k] > j[k])
    swap(i[k], j[k])
  else
    j[k] = j[k] + 1
  end
  x = (x + d) % (n * (n - 1))
end

Input

$N$
$s_1$
$\vdots$
$s_N$
$M$ $x$ $d$

(Corrected on 2017/5/5 22:46: the minimum value of N was changed from 1 to 2)
$2 \le N \le 100000 = 10^5$
$|s_i| \ge 1$ for all $1 \le i \le N$
$\sum_{i} |s_i| \le 800000 = 8 \times 10^5$
Each $s_i$ consists of lowercase Latin letters ('a' to 'z').
$1 \le M \le 3000000 = 3 \times 10^6$
$0 \le x < N(N - 1)$
$0 \le d < N(N - 1)$
$x$,$d$ are integers.

Output

For each $k$, compute the length of the longest common prefix of $s_{i_k}$ and $s_{j_k}$, and output the sum of these lengths on one line, followed by a newline.

Sample

4
kinesis
koba
variance
kobushu
3 1 2

4

5
aaaaa
dadad
aaaab
abcbc
aaaac
4 1 1

9