Number of palindromes

Input

The first line of the input contains the string $S$, consisting only of lowercase Latin letters. The string $S$ is guaranteed to be non-empty, with a length $N$ not exceeding $4000$. The next $N$ numbers, ranging from $1$ to $N$, represent the indices of the characters to be replaced with "?".

Initially, output the number of palindromic substrings in the string $S$.

Then, perform the following sequence of actions $N$ times:

1. Read the number $K$, which is the index of the character in the string to be replaced with "?" at the current step (1 \le K \le N).

2. Calculate the number of palindromic substrings in the current version of the string.

3. Output this number on a separate line.

It is guaranteed that no character in the given string will be replaced with "?" more than once.

Output

Refer to the input data description for output details.

Note: In the string "abac", the palindromic substrings are $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, $(1,3)$. After replacing the third character with "?", the string becomes "ab?c", with palindromic substrings $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, $(1,3)$, $(2,3)$, $(3,4)$. After replacing the second character with "?", the string becomes "a??c", where only the substring $(1,4)$ is not a palindrome. With further replacements, all substrings will be palindromes.

Examples