31794번 - 두유노팰린드롬?

문제

문자열 $S$가 주어질 때 $S$의 부분문자열이면서 팰린드롬인 것을 부분팰린드롬이라 한다. 이때 아래 질의를 수행하는 프로그램을 작성하시오.

• $x$: 문자열 $S$의 $x$번째 문자가 몇 개의 부분팰린드롬에 포함되는지 출력한다.

입력

첫 번째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다. $(1 \leq |S| \leq 10^6)$

두 번째 줄에 질의의 개수 $Q$가 주어진다. $(1 \leq Q \leq 2 \times 10 ^ {5} )$

세 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 한 줄에 하나씩 주어진다. $(1 \leq x \leq |S|)$

출력

질의가 주어질 때마다 질의의 결과를 순서대로 한 줄에 하나씩 출력한다.

제한

노트

팰린드롬이란 앞에서 읽었을 때와 뒤에서 읽었을 때가 같은 문자열이다.

부분문자열이란 문자열의 연속된 일부를 의미한다. 예를 들어 abcde는 abcdefe, eeabcde의 부분문자열이지만 abbccdde의 부분문자열은 아니다.

문자열 $S$의 부분 문자열 $S_{l} S_{l+1} \cdots S_{r-1} S_{r}$이 부분팰린드롬 $T$일 때 $S_{i} (l \leq i \leq r)$는 부분팰린드롬 $T$에 포함된다고 한다.