시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 7 4 2 50.000%

문제

모의고사를 개최하고 싶었으나 낼 문제가 없었던 운영진은 생각나는 키워드인 '팰린드롬'과 '자료구조'를 혼합한 문제를 출제하기로 했습니다.

승현이는 여러분을 위해 알파벳 소문자로만 구성된 문자열 S를 만들었습니다. 편의상 S[i..j]를 S의 i번째 문자, (i+1)번째 문자, ..., (j−1)번째 문자, j번째 문자를 이어 붙인 부분문자열로 정의합시다. (단 1≤i≤j≤|S|)

여러분이 할 일은 S[a..b] (단 a≤b)의 부분문자열에서 팰린드롬이 몇 개나 있는지 세는 것입니다. 다시 말해, a≤x≤y≤b이고 S[x..y]가 팰린드롬인 두 정수의 순서쌍 (x,y)의 개수를 찾아내면 됩니다.

입력

첫 번째 줄에 승현이가 만들어낸 문자열 S (1≤|S|≤100,000)가 주어집니다. 이 문자열은 알파벳 소문자 ('a', 'b', ..., 'z')로만 구성되어 있습니다.

두 번째 줄에 질의의 수 Q (1≤Q≤300,000)가 주어집니다. 다음 Q개 줄에 두 개의 정수 ai와 bi (1≤ai≤bi≤|S|)가 주어집니다. 각 질의에 대해서 여러분은 S[ai..bi]의 부분문자열들 중에 팰린드롬이 몇 개인지 세어야 합니다.

출력

각 질의가 주어질 때마다 S[ai..bi]의 부분문자열들 중에 팰린드롬이 몇 개나 있는지 한 줄에 하나씩 출력합니다.

 

예제 입력

abcba
3
1 5
2 4
2 3

예제 출력

7
4
2

힌트

어떤 문자열 T=t1t2t3⋯tn이 팰린드롬이라는 것은 이것을 앞에서부터 뒤로 읽으나 뒤에서부터 앞으로 읽으나 같게 읽히는 것을 의미합니다. 즉,

t1t2t3⋯tn−1tn=tntn−1⋯t3t2t1

를 만족하는 T는 팰린드롬입니다.

|S|는 문자열 S의 길이입니다.