 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
First qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  3 seconds 

Memory limit  256 megabytes 
Ilya is working for Laboratory of Investigation of String Algorithms (LISA). Now he is trying to solve the following problem.
You are given an array of strings s_{1}, s_{2}, ..., s_{n}, and q queries. Each query is specified by two integers: l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n). To answer the query you must do the following. Let us call a string representable if it is possible to obtain it using the following method: take two strings s_{x} and s_{y}, where l_{i} ≤ x, y ≤ r_{i}, take nonempty prefix of s_{x} and nonempty suffix of s_{y}, concatenate them. The answer to the query is the number of different representable strings for given l_{i} and r_{i}.
For example, consider s = [abc, ab, ac, bcac], take l_{i} = 2, r_{i} = 3. The following strings are representable:
x = 2, y = 2: ab = a + b, aab = a + ab, abb = ab + b, abab = ab + ab.
x = 2, y = 3: ac = a + c, aac = a + ac, abc = ab + c, abac = ab + ac.
x = 3, y = 2: ab = a + b, aab = a + ab, acb = ac + b, acab = ac + ab.
x = 3, y = 3: ac = a + c, aac = a + ac, acc = ac + c, acac = ac + ac.
So there are 12 different representable strings.
Help Ilya to solve the problem as fast as you can.
Input format 
The first line of input contains two integers: n and q — the number of strings and the number of queries (1 ≤ n, q ≤ 10^{5}). Each of the following n string contains nonempty words s_{i}, that consist of lowercase English letters. The sum of their lengths doesn't exceed 10^{5}. The following q lines contain queries: each line contains two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — parameters of the ith query. 

Output format 
Output q lines, the ith of them must contain one integer — the answer to the ith query. 
Examples 
Input data
4 3 abc ab ac bcac 3 4 1 3 2 3
Output data
20 23 12 
