LISA

일리야는 문자열 알고리즘 연구소(LISA)에서 일한다. 지금 그는 다음 문제를 풀고 있다.

문자열 배열 $s_1, s_2, \ldots, s_n$과 $q$개의 질의가 주어진다. 각 질의는 두 정수 $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$)로 주어진다. 질의에 답하려면 다음 방법으로 만들 수 있는 문자열을 세야 한다. $l_i \le x, y \le r_i$를 만족하는 두 문자열 $s_x$, $s_y$를 고른다. $s_x$의 비어 있지 않은 접두사와 $s_y$의 비어 있지 않은 접미사를 가져와 이어 붙인다. 이렇게 만든 문자열을 표현 가능한 문자열이라고 한다. 질의의 답은 $l_i$, $r_i$에 대해 서로 다른 표현 가능한 문자열의 개수다.

예를 들어 $s = [abc, ab, ac, bcac]$이고 $l_i = 2$, $r_i = 3$이라고 하자. 다음 문자열은 표현 가능하다.

$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.

따라서 서로 다른 표현 가능한 문자열은 12개다.

첫 줄에 두 정수 $n$, $q$가 주어진다. 각각 문자열의 개수와 질의의 개수다 ($1 \le n, q \le 10^5$). 다음 $n$개의 줄에는 비어 있지 않은 단어 $s_i$가 하나씩 주어진다. 단어는 영소문자로만 이루어진다. 모든 단어 길이의 합은 $10^5$을 넘지 않는다. 다음 $q$개의 줄에는 두 정수 $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$)가 주어진다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 출력한다.