Кількість паліндромів#4676

Кількість паліндромів

1 секунда

64 мегабайти

Середня

Степан на уроках інформатики почав вивчати властивості паліндромів. Нагадаємо, що рядок називається паліндромом, якщо він дорівнює перевернутому рядку. Оскільки Степан швидко знайшов всі підрядки даного рядка, що є паліндромами, то він вирішив ускладнити собі завдання, а саме він по черзі замінює символи у рядку на символ "?", який він вважає рівним будь-якому символу. Наприклад, Степан вважає рівними рядки "ABA" і "A?A", "ABB" і "AB?", а рядки "AB?", "ABC??" та "?C?" він вважає паліндромами.

Степан хоче після кожної заміни символу на "?" визначати кількість підрядків рядка $S$ , що є паліндромами (звісно в тому, як це розуміє сам Степан). До того ж Степан вважає підрядки різними, якщо у них відрізняються позиції початку і/або кінця.

Напишіть програму, яка автоматизує дії Степана, щоб він нарешті зайнявся чимось іншим.

Вхідні дані

Перший рядок вхідного файлу містить рядок $S$ , що містить тільки маленькі латинські букви. Гарантується, що рядок $S$ непорожній, і його довжина $N$ не перевищує $4000$ . Далі міститься $N$ чисел від $1$ до $N$ – номери символів, які замінюються на "?".

Після зчитування рядка $S$ виведіть кількість його підрядків, що є паліндромами.

Далі ви повинні $N$ разів виконати таку послідовність дій:

Зчитати число $K$ – номер символу рядка, який замінюють на "?" на поточному кроці ( $1 \leq K \leq N$ 1 \le K \le N).
Підрахувати кількість підрядків поточного рядка, що є паліндромами.
Вивести це число у окремому рядку.

Гарантується, що ніякий символ даного рядка не буде двічі замінено на "?".

Вихідні дані

Дивіться опис у вхідних даних.

Примітка: У рядку "abac" паліндромами є підрядки $(1, 1)$ , $(2, 2)$ , $(3, 3)$ , $(4, 4)$ , $(1, 3)$ . Після заміни третього символу на "?" маємо рядок "ab?c", в якому паліндромами є $(1, 1)$ , $(2, 2)$ , $(3, 3)$ , $(4, 4)$ , $(1, 3)$ , $(2, 3)$ , $(3, 4)$ . Після заміни другого символу на "?" маємо рядок "a??c", в якому паліндромами не є тільки підрядок $(1, 4)$ . Після наступних замін всі підрядки будуть паліндромами.

Приклади

Приклад 1