Степан на уроках інформатики почав вивчати властивості паліндромів. Нагадаємо, що рядок називається паліндромом, якщо він дорівнює перевернутому рядку. Оскільки Степан швидко знайшов всі підрядки даного рядка, що є паліндромами, то він вирішив ускладнити собі завдання, а саме він по черзі замінює символи у рядку на символ "?", який він вважає рівним будь-якому символу. Наприклад, Степан вважає рівними рядки "ABA" і "A?A", "ABB" і "AB?", а рядки "AB?", "ABC??" та "?C?" він вважає паліндромами.
Степан хоче після кожної заміни символу на "?" визначати кількість підрядків рядка S, що є паліндромами (звісно в тому, як це розуміє сам Степан). До того ж Степан вважає підрядки різними, якщо у них відрізняються позиції початку і/або кінця.
Напишіть програму, яка автоматизує дії Степана, щоб він нарешті зайнявся чимось іншим.
Перший рядок вхідного файлу містить рядок S, що містить тільки маленькі латинські букви. Гарантується, що рядок S непорожній, і його довжина N не перевищує 4000. Далі міститься N чисел від 1 до N – номери символів, які замінюються на "?".
Після зчитування рядка S виведіть кількість його підрядків, що є паліндромами.
Далі ви повинні N разів виконати таку послідовність дій:
Зчитати число K – номер символу рядка, який замінюють на "?" на поточному кроці (1 ≤ K ≤ 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). Після наступних замін всі підрядки будуть паліндромами.