16259번 - LISA 다국어

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₁, s₂, ..., 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 non-empty prefix of s_x and non-empty 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.

The first line of input contains two integers: n and q — the number of strings and the number of queries (1 ≤ n, q ≤ 10⁵).

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 10⁵.

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

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