Common Substring Queries

Given $N$ strings $S_1, \dots, S_N$ made only of lowercase English letters, write a program that processes the following query.

• $i\ j$: Find the number of distinct common substrings of $S_i$ and $S_j$.

A substring of a string is a non-empty contiguous part of that string. A common substring of two strings $A$ and $B$ is a string that is a substring of both $A$ and $B$.

The first line contains the number of strings $N$ ($1 \leq N \leq 200\,000$). The next $N$ lines each contain one string $S_1, \dots, S_N$ made of lowercase letters, one per line. The total length of $S_1, \dots, S_N$ does not exceed $200\,000$.

The next line contains the number of queries $Q$ ($1 \leq Q \leq 200\,000$). The next $Q$ lines each contain two integers $i$ and $j$ ($1 \leq i, j \leq N$).

Print the answer to each of the $Q$ queries on its own line, in order.