두유노팰린드롬?

문자열 $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$에 포함된다고 한다.