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

Input	Output
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=2$. $1^{\text{st}}$string $s_1$is abc, $2^\text{nd}$ string $s_2$ is bca, and $s_{1}[2\ldots 3]=\text{bc}$. Now, for the first query, we need to find the number of times bc occurs in $s_2$, which occurs only in $s_2[1\ldots 2]$. Hence the answer to the first query is $\boxed{1}$.