Description

yz is the leader of Country Z. He requires that the name of each region can only be one of the $26$ lowercase Latin letters. Since the number of regions may exceed $26$, a problem arises: how can we tell regions with the same name apart? Therefore, yz specifies that the description of a region must include all of its superiors, and the superiors must be listed in order. Thus, a region’s description is a string. For example, if a region’s name is $\tt c$, its superior is $\tt b$, the superior of $\tt b$ is $\tt a$, and $\tt a$ has no superior, then this region is described as $\tt abc$. Clearly, this description also contains the descriptions of $\tt c$’s superior $\tt b$ and $\tt b$’s superior $\tt a$, which are $\tt ab$ and $\tt a$, respectively.

Note that each region has at most one superior. Among regions with the same superior, their names are different. Among regions with no superior, their names are also different.

Now, yz has published the descriptions of $n$ regions to the public. These descriptions include the descriptions of all regions in Country Z, and you are asked to handle visitors’ travel problems.

There are $m$ pairs of people visiting this country. For each pair, the first person likes the $j$-th region in the $i$-th description; let this region’s description be $s_1$. The second person likes the $l$-th region in the $k$-th description; let this region’s description be $s_2$. To unify their itinerary, they decide to visit the region whose description is $s$ (obviously, they only care about the region name, not the region itself). Let the length of $s$ be $t$. The string $s$ must satisfy:

1. $t\leq j$, $t\leq l$.
2. $s[1\cdots t]=s_1[j-t+1\cdots j]$, $s[1\cdots t]=s_2[l-t+1\cdots l]$, i.e., $s$ is a common suffix of the prefix $s_1[1\cdots j]$ and the prefix $s_2[1\cdots l]$.
3. Maximize $t$.

To avoid overly large output, you only need to convert this string into a base-$26$ number (as generated below), then convert it to base $10$ and output it modulo $(10^9+7)$:

• $a \to 0$;
• $b \to 1$;
• ……
• $z \to 25$.

For example, region $\tt cab$ is encoded as $2\times26^2+0\times26^1+1\times26^0=1353$.

Input Format

The first line contains an integer $n$.

Lines $2$ to $n+1$: the $(i+1)$-th line contains a string $a_i$, representing the $i$-th description.

The next line contains an integer $m$.

The next $m$ lines each contain four integers $i,j,k,l$, with the meanings consistent with the statement.

Output Format

There are $m$ lines. Each line contains one integer, which is the encoding of the answer string.

2
aabb
babb
2
1 3 2 3
1 4 2 4 

1
1

Hint

Sample Explanation

In query $1$, the common suffixes include $\tt ab$ and $\tt b$, but there is no region $\tt ab$, only region $\tt b$, so they can only choose region $\tt b$.

In query $2$, the common suffixes include $\tt abb$, $\tt bb$, and $\tt b$, but there are no regions $\tt abb$ or $\tt bb$, only region $\tt b$, so they can only choose region $\tt b$.

Constraints and Notes

Let the total number of regions in this country be $tot$ (note that the total length of input strings may exceed $tot$!).

• For $30\%$ of the testdata, $1\le tot, m, n \le 100$.
• For $50\%$ of the testdata, $1\le tot, m, n \le 1000$.
• For $80\%$ of the testdata, $1\le tot, m, n \le 10^5$.
• For $100\%$ of the testdata, $1\le tot, m, n \le 10^6$.

It is guaranteed that the input file does not exceed $20\text{MB}$.

HEOI2012 Day 2 Task 2.

Translated by ChatGPT 5