Longest Common Suffix Encoding

In country Z, every region is identified by a single lowercase Latin letter. However, since there can be more than 26 regions, leader yz decided that the full description of a region must include the names of all its ancestors arranged in order. For example, if a region has name c, its parent has name b and the grandparent has name a (with a having no parent), then the description of the region is abc. Note that such a description implicitly contains the descriptions of its ancestors: ab and a.

It is guaranteed that each region has at most one parent, regions with the same parent have different names, and regions without a parent have distinct names.

yz published n description strings, which together include the descriptions of all regions of country Z. Then, there are m queries regarding travel plans. In each query, two people select a region based on these descriptions as follows:

• The first person chooses the region represented by the first j characters of the i-th description (that is, the region at position j in the chain of the i-th description).
• The second person chooses the region represented by the first l characters of the k-th description.

Let the two chosen region descriptions be \(s_1\) and \(s_2\). They agree to visit a region whose description is \(s\) of length \(t\) such that:

1. \(t \leq j\) and \(t \leq l\).
2. \(s\) is equal to the last \(t\) characters of \(s_1\) and also equal to the last \(t\) characters of \(s_2\); in other words, \(s\) is the longest common suffix of the prefixes chosen.

After determining \(s\), convert it into an integer by interpreting it as a base-26 number with the following mapping:

• a \to 0
• b \to 1
• ...
• z \to 25

For example, the region cab is encoded as:

[ 2\times26^2 + 0\times26^1 + 1 \times26^0 = 1353 ]

Output the resulting number modulo \(10^9+7\).

inputFormat

The first line contains an integer n (1 \leq n \leq 10^5), the number of region description strings.

Each of the following n lines contains a non-empty string consisting only of lowercase letters, representing a region's full description. It is guaranteed that if a string has length L, then the first L characters form the complete description of one region (and every prefix of a full description corresponds to a valid region).

The next line contains an integer m (1 \leq m \leq 10^5), the number of queries.

Each of the following m lines contains four integers: i j k l (1-indexed). The first person picks the region corresponding to the first j characters of the i-th description and the second person picks the region corresponding to the first l characters of the k-th description. It is guaranteed that the chosen prefixes exist in their respective strings.

outputFormat

For each query, output a single line with the integer resulting from converting the longest common suffix (as described above) into a base-26 number modulo \(10^9+7\). If there is no common suffix, output 0.

sample

3
abc
bcd
cde
3
1 3 2 2
2 3 3 2
1 1 3 1

28
55
0

</p>