Substring Search

steinum SEC Inter University Juni...
Limits 1s, 512 MB

You are given nn strings s1,s2,s3,,sns_1, s_2, s_3, \ldots, s_n and should process mm queries. Each query is described by four integers i,l,r,ji,l,r,j. It means that you need to find how many times substring si[lr]s_i[l\ldots r] occurs in sjs_j.


  • Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position 33 and ends in position 66), but "aa" or "d" isn't substrings of this string. So the substring of the string aa from position ll to position rr is a[lr]=alal+1ara[l\ldots r]=a_{l}a_{l+1}\ldots a_{r}.

Input

The first line of the input contains an integer n(1n105)n(1\le n \le 10^5)— number of strings.

Each of the following nn lines contains a string sis_i of lowercase Latin letters. It is guaranteed that sum of all the strings is no more than 10510^5.

The following line contains an integer m(1m105)m(1\le m \le 10^5)— number of queries.

Each of the following mm lines contains four integers i,l,r,j(1i,jn,1lrsi)i, l, r, j(1\le i, j\le n, 1\le l \le r\le |s_i|) as mentioned in the statement. Note that, all the indices are 11-based and ii might be equal to jj.

Output

For each query, print a single integer — the answer to the problem.

Sample

InputOutput
2
abc
bca
2
1 2 3 2
1 1 2 2
1
0

In the first query, i=1,l=2,r=3,j=2i=1, l=2, r=3, j=2. 1st1^{\text{st}}string s1s_1is abc, 2nd2^\text{nd} string s2s_2 is bca, and s1[23]=bcs_{1}[2\ldots 3]=\text{bc}.
Now, for the first query, we need to find the number of times bc occurs in s2s_2, which occurs only in s2[12]s_2[1\ldots 2]. Hence the answer to the first query is 1\boxed{1}.


Submit

Login to submit.

Statistics

33% Solution Ratio
ash_98Earliest, 1M ago
AMDAD_MBSTUFastest, 0.0s
AMDAD_MBSTULightest, 32 kB
AMDAD_MBSTUShortest, 4197B
Toph uses cookies. By continuing you agree to our Cookie Policy.