Строка \(t\) считается \(k\)-хорошей, если существует хотя бы одна подстрока\(^\dagger\) длины \(k\), которая не является палиндромом\(^\ddagger\). Пусть \(f(t)\) обозначает сумму всех значений \(k\), при которых строка \(t\) является \(k\)-хорошей.
Вам дана строка \(s\) длины \(n\). Вы должны ответить на \(q\) следующих запросов:
- Для данных \(l\) и \(r\) (\(l < r\)), найдите значение \(f(s_ls_{l + 1}\ldots s_r)\).
\(^\dagger\) Подстрока строки \(z\) — это последовательность подряд идущих символов строки \(z\). Например, «\(\mathtt{defor}\)», «\(\mathtt{code}\)» и «\(\mathtt{o}\)» являются подстроками «\(\mathtt{codeforces}\)», а «\(\mathtt{codes}\)» и «\(\mathtt{aaa}\)» не являются.
\(^\ddagger\) Палиндром — это строка, которая одинаково читается как слева направо, так и справа налево. Например, строки «\(\texttt{z}\)», «\(\texttt{aa}\)» и «\(\texttt{tacocat}\)» являются палиндромами, а «\(\texttt{codeforces}\)» и «\(\texttt{ab}\)» — нет.
Выходные данные
Для каждого запроса выведите \(f(s_ls_{l + 1}\ldots s_r)\).
Примечание
В первом запросе первого набора входных данных строка равняется \(\mathtt{aaab}\). Подстроки \(\mathtt{aaab}\), \(\mathtt{aab}\) и \(\mathtt{ab}\) не являются палиндромами и имеют длины \(4\), \(3\) и \(2\) соответственно. Таким образом, строка является \(2\)-хорошей, \(3\)-хорошей и \(4\)-хорошей. Следовательно, \(f(\mathtt{aaab}) = 2 + 3 + 4 = 9\).
Во втором запросе первого набора строка имеет вид \(\mathtt{aaa}\). В ней нет непалиндромных подстрок. Следовательно, \(f(\mathtt{aaa}) = 0\).
В первом запросе второго набора входных данных строка имеет вид \(\mathtt{abc}\). Подстроки \(\mathtt{ab}\), \(\mathtt{bc}\) и \(\mathtt{abc}\) не являются палиндромами и имеют длины \(2\), \(2\) и \(3\) соответственно. Таким образом, строка является \(2\)-хорошей и \(3\)-хорошей. Следовательно, \(f(\mathtt{abc}) = 2 + 3 = 5\). Заметим, что даже если существует \(2\) непалиндромных подстроки длины \(2\), мы считаем их только один раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 4
aaab
1 4
1 3
3 4
2 4
3 2
abc
1 3
1 2
5 4
pqpcc
1 5
4 5
1 3
2 4
2 1
aa
1 2
12 1
steponnopets
1 12
|
9
0
2
5
5
2
14
0
2
5
0
65
|