Substring Search

You are given $n$ strings $s_1, s_2, s_3, \ldots, s_n$ and should process $m$ queries. Each query is described by four integers $i,l,r,j$. It means that you need to find how many times substring $s_i[l\ldots r]$ occurs in $s_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 $3$ and ends in position $6$), but "aa" or "d" isn't substrings of this string. So the substring of the string $a$ from position $l$ to position $r$ is $a[l\ldots r]=a_{l}a_{l+1}\ldots a_{r}$.

Input

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

Each of the following $n$ lines contains a string $s_i$ of lowercase Latin letters. It is guaranteed that sum of all the strings is no more than $10^5$.

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

Each of the following $m$ lines contains four integers $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 $1$-based and $i$ might be equal to $j$.

Output

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

Sample

2
abc
bca
2
1 2 3 2
1 1 2 2

1
0