Степан на уроках информатики начал изучать свойства палиндромов. Напомним, что строка называется палиндромом, если она равна перевёрнутой строке. Так как Степан быстро нашёл все подстроки заданной строки, являющиеся палиндромами, он решил усложнить своё задание, а именно он по очереди изменяет символы в строке на символ "\textbf{?}", который он считает равным любому символу. Например, Степан считает равными строки "\textbf{ABA}" и "\textbf{A?A}", "\textbf{ABB}" и "\textbf{AB?}", а строки "\textbf{AB?}", "\textbf{ABC??}" и "\textbf{?C?}" он считает палиндромами. Степан хочет после каждой замены символа на "\textbf{?}" определить количество подстрок стродиа \textbf{S}, являющиеся палиндромами (естественно, как это понимает сам Степан). К тому же Степан считает подстроки разными, если в них отличаются позиции начала и/или конца. Напишите программу, автоматизирующую действия Степана, чтобы он наконец-то смог заняться чем-то другим. \InputFile Первая стока входного файла содержит стрку \textbf{S}, содержащую только маленькие латинские буквы. Гарантируется, что строка \textbf{S} непуста, и её длина \textbf{N} не превышает \textbf{4000}. Далее содержится \textbf{N} чисел от \textbf{1} до \textbf{N} -- номера символов, изменяющиеся на "\textbf{?}". После считывания строки \textbf{S} выведите количество её подстрок, являющихся палиндромами. Далее вы должны \textbf{N} раз выполнить следующую последовательность действий: \begin{enumerate} \item Считать число \textbf{K} -- номер символа строки, который изменяется на "\textbf{?}" на текущем шаге (\textbf{1} ≤ \textbf{K} ≤ \textbf{N}). \item Подсчитать количество подстрок текущей строки, являющихся палиндромами. \item Вывести это число в отдельной строке. \end{enumerate} Гарантируется, что никакой символ заданной строки не будет дважды изменён на "\textbf{?}". \OutputFile Смотрите описание входных данных. \textit{\textbf{Примечание}}: В строке "\textbf{abac}" палиндромами являются подстроки \textbf{(1, 1)}, \textbf{(2, 2)}, \textbf{(3, 3)}, \textbf{(4, 4)}, \textbf{(1, 3)}. После замены третьего символа на "\textbf{?}" имеем строку "\textbf{ab?c}", в ней палиндромами являются \textbf{(1, 1)}, \textbf{(2, 2)}, \textbf{(3, 3)}, \textbf{(4, 4)}, \textbf{(1, 3)}, \textbf{(2, 3)}, \textbf{(3, 4)}. После замены второго символа на "\textbf{?}" имеем строку "\textbf{a??c}", в которой палиндромом не является только подстрока \textbf{(1, 4)}. После последующих замен все подстроки будут палиндромами.