Concatenated Substrings Query

We are given n strings \(s_1,s_2,\dots,s_n\) and \(q\) queries. The strings are 1-indexed. For two strings, we define their sum as the concatenation of the first string and the second string (i.e. appending the second to the first).

Define a function \[ f(a,b,c)=\sum_{i=1}^{|a|}\sum_{j=i}^{|a|}\sum_{k=1}^{|b|}\sum_{l=k}^{|b|} \Bigl[ a_{i,i+1,\dots,j}+b_{k,k+1,\dots,l} = c \Bigr], \] where \(a\), \(b\) and \(c\) are strings and \(a+b\) denotes the concatenation of two nonempty substrings selected respectively from \(a\) and \(b\) that equal \(c\). In other words, if we denote by \([a=b]\) the indicator that is 1 if \(a=b\) and 0 otherwise, then for strings \(a\), \(b\) and \(c\) (with \(|c|\ge2\)) we have \[ f(a,b,c)=\sum_{p=1}^{|c|-1} \Bigl(\text{\# of occurrences of }c[1:p]\text{ in }a\Bigr)\cdot \Bigl(\text{\# of occurrences of }c[p+1:|c|]\text{ in }b\Bigr). \]

There are \(q\) queries. In each query, you are given three positive integers \(l, r, k\). You need to output \[ \sum_{i=l}^{r}\sum_{j=l}^{r} f(s_i,s_j,s_k). \]

Note: Each substring considered is nonempty and the indices in the strings are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

The following \(n\) lines each contain a string \(s_i\).

Each of the next \(q\) lines contains three integers \(l\), \(r\) and \(k\) separated by spaces.

outputFormat

For each query, output a single line containing one integer: the answer to the query.

sample

3 2
ab
a
aba
1 2 1
1 3 3

2
12