Description

给定一个串\(S\)和多组询问\((l_i, r_i)\)，问\(S[l_i..r_i]\)的所有子串的Border总数是多少。

Input

• 第一行两个数\(n\le 2000, q\le 100000\)，表示字符串长度和询问数；
• 第二行一个长度为\(n\)的仅包含小写英文字母的字符串；
• 下面\(q\)行，每行两个正整数\(l_i, r_i\)，表示一组询问。

Output

• 输出共\(q\)行，对于每一组询问\(l_i, r_i\)，输出一行答案，为\(S[l_i, r_i]\)所有子串的Border总数

Sample

Input

5 4
ababa
1 5
1 3
1 4
2 4

Output

7
1
3
1

Hint

• 对于第三组询问\((1, 4)\)，\(abab\)所有有Border的子串为：\(aba\)一个，\(bab\)一个，\(abab\)一个，共三个。
• 10个测试点数据规模如下：
• n = 10, 30, 50, 100, 100, 1000, 2000, 2000, 2000, 2000
• q = 10, 30, 100, 1000, 1000, 10000, 100000, 100000, 1, 100000