LISA

Ilya works at the Laboratory of Investigation of String Algorithms (LISA). He is trying to solve the following problem.

You are given an array of strings $s_1, s_2, \ldots, s_n$ and $q$ queries. Each query is given by two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$). To answer a query, consider the strings that can be built as follows. Choose two strings $s_x$ and $s_y$ with $l_i \le x, y \le r_i$. Take a non-empty prefix of $s_x$ and a non-empty suffix of $s_y$, and concatenate them. Call such a string representable. The answer to the query is the number of distinct representable strings for $l_i$ and $r_i$.

For example, let $s = [abc, ab, ac, bcac]$ and $l_i = 2$, $r_i = 3$. The following strings are representable.

For $x = 2$, $y = 2$: ab = a + b, aab = a + ab, abb = ab + b, abab = ab + ab. For $x = 2$, $y = 3$: ac = a + c, aac = a + ac, abc = ab + c, abac = ab + ac. For $x = 3$, $y = 2$: ab = a + b, aab = a + ab, acb = ac + b, acab = ac + ab. For $x = 3$, $y = 3$: ac = a + c, aac = a + ac, acc = ac + c, acac = ac + ac.

So there are 12 distinct representable strings.

The first line contains two integers $n$ and $q$, the number of strings and the number of queries ($1 \le n, q \le 10^5$). Each of the next $n$ lines contains a non-empty word $s_i$ made of lowercase English letters. The total length of all words does not exceed $10^5$. Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

Print $q$ lines. The $i$-th line contains the answer to the $i$-th query.