Number of palindromes

Stepan has been exploring palindromes in his computer science class. A string is a palindrome if it reads the same forwards and backwards. After quickly identifying all palindromic substrings in a given string, Stepan decided to make the task more challenging. He began replacing characters in the string with the character "?", which he treats as equivalent to any character. For instance, Stepan considers the strings "ABA" and "A?A", "ABB" and "AB?" as equivalent, and he regards the strings "AB?", "ABC??", and "?C?" as palindromes.

Stepan's goal is to find out how many substrings of the string S are palindromes (according to his definition) after each character replacement with "?". He considers substrings distinct if they have different starting or ending positions.

Your task is to write a program that automates Stepan's process, allowing him to focus on other activities.

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 ≤ K ≤ 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