C. Echoes of the Jade Library
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After a mission between Shanghai and Tianjin, the spy Lian returns to his hidden base in the alleys of Shanghai. There, he receives a new assignment: to become the Guardian of the legendary Jade Library, concealed in the Longmen Valley.

The library holds $$$N$$$ scrolls, numbered from $$$1$$$ to $$$N$$$, each containing a string composed only of lowercase English letters. According to the court magicians, certain palindromic substrings hidden in these texts encode ancient instructions and magical secrets. Preserving the library means correctly identifying where and how many of these palindromes exist.

Lian must therefore answer $$$Q$$$ real-time queries. Each query defines an interval $$$[L, R]$$$ of scrolls and asks for the number of distinct palindromic substrings (of length $$$\geq 1$$$) that occur in at least one of the texts within that interval. Any incorrect response may trigger traps left by the library's ancient protectors.

These queries are made in real time and expect an immediate response.

Note: A palindrome is a sequence of letters that reads the same from left to right and from right to left. Examples: a, aa, aba, abba. Only palindromic substrings (i.e., contiguous segments) are considered.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 2 \cdot 10^5$$$) — the number of scrolls and the number of magical queries.

The next $$$N$$$ lines contain the arcane texts $$$s_1, s_2, \dots, s_N$$$, each consisting of lowercase English letters a–z. No string is empty, and the total number of characters across all strings does not exceed $$$5 \cdot 10^5$$$.

Each of the following $$$M$$$ lines contains two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$), representing the range of scrolls the magi wish to examine.

Output

For each query, output a single line with the number of distinct palindromic substrings found in at least one of the strings from index $$$L$$$ to $$$R$$$, inclusive.

Remember: Since the queries are online, you must flush the output after each line (e.g., fflush(stdout) in C or cout.flush() in C++).

Example
Input
3 3
abc
aaa
aba
1 2
2 3
1 3
Output
5
5
6