Степан на уроках інформатики почав вивчати властивості паліндромів. Нагадаємо, що рядок називається паліндромом, якщо він дорівнює перевернутому рядку. Оскільки Степан швидко знайшов всі підрядки даного рядка, що є паліндромами, то він вирішив ускладнити собі завдання, а саме він по черзі замінює символи у рядку на символ "\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)}. Після наступних замін всі підрядки будуть паліндромами.