题目描述

本题有对应的Easy Version，区别仅在Easy为单组查询，Hard为多组，保证Easy的测试用例集为Hard的子集。

智乃在练习打字，她打开电脑上的记事本，准备输入一系列单词组成的集合，她想要知道如果想在记事本上显示过这个单词集合中所有的单词，则最少敲多少下键盘？

具体来讲，智乃只能使用键盘上的 26 个英文字母和退格符。在题干中，为了便于观察，我们使用 $\backslash b$ 表示退格符，输入后会删除记事本上最后一个字符。 例如，当前的单词集合是 给定集合 {$\texttt{nowcoder},\texttt{nowdays},\texttt{now}$}，则在键盘上依次输入 $\texttt{nowdays}\backslash b \backslash b \backslash b \backslash b \texttt{coder}$。就可以完成在记事本上显示过 $\texttt{nowcoder},\texttt{nowdays},\texttt{now}$ 三个单词的目标，只要求在输入的过程中存在过这几个单词就算完成目标，没有先后顺序。

现在有 $n$ 个单词，编号从 1 到 $n$，智乃有 $m$ 次查询，每次查询单词集合为 $l$ 到 $r$ 时，要想在记事本上显示过所有单词，至少要敲几下键盘？ 注意：记事本上显示某个单词指的是在某个时刻，记事本上仅显示该单词，不包括以子串的形式显示。敲一次退格符视为敲一下键盘。 第一行输入两个正整数 $n,m\left(1\leq n,m \leq 10^5\right)$ 代表单词的数目、查询的数目。 此后 $n$ 行，第 $i$ 行输入一个仅由小写英文字母组成的单词 $s_i$。 最后输入 $m$ 行，每行输入两个正整数 $l_i,r_i\left(1 \le l_i\le r_i \le n\right)$ 代表一次查询。

除此之外，保证单个测试文件中出现的小写字母数量 $\textstyle\sum |s_i|$ 之和不超过 $10^6$。 对于每一次查询，新起一行。输出一个整数，代表最少需要敲几次键盘。

输入描述

第一行输入两个正整数 $n,m\left(1\leq n,m \leq 10^5\right)$ 代表单词的数目、查询的数目。 此后 $n$ 行，第 $i$ 行输入一个仅由小写英文字母组成的单词 $s_i$。 最后输入 $m$ 行，每行输入两个正整数 $l_i,r_i\left(1 \le l_i\le r_i \le n\right)$ 代表一次查询。

输出描述

对于每一次查询，新起一行。输出一个整数，代表最少需要敲几次键盘。

样例1

输入

3 3
nowcoder
nowdays
now
1 3
1 2
3 3

输出

16
16
3

样例2

输入

4 1
nowcoder
nowdays
days
coder
1 4

输出

34