First qualification round completed

Tasks

Show one task per page / all tasks on one page

"E" LISA
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 s1, s2, ..., sn, and q queries. Each query is specified by two integers: li and ri (1 ≤ li ≤ ri ≤ 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 sx and sy, where li ≤ x, y ≤ ri, take non-empty prefix of sx and non-empty suffix of sy, concatenate them. The answer to the query is the number of different representable strings for given li and ri.

For example, consider s = [abc, ab, ac, bcac], take li = 2, ri = 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 ≤ 105).

Each of the following n string contains non-empty words si, that consist of lowercase English letters. The sum of their lengths doesn't exceed 105.

The following q lines contain queries: each line contains two integers li, ri (1 ≤ li ≤ ri ≤ n) — parameters of the i-th query.

Output format

Output q lines, the i-th of them must contain one integer — the answer to the i-th query.

Examples
Input data
4 3
abc
ab
ac
bcac
3 4
1 3
2 3
Output data
20
23
12
 

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?

Registration

The instruction for password recovery
has been sent to your email