Palindromların sayı
Stepan informatika dərslərində palindromların xüsusiyyətlərini öyrənməyə başladı. Xatırladaq ki, bir sıra öz əksinə çevrildikdə eyni qalırsa, o, palindrom adlanır. Stepan tez bir zamanda verilmiş sıranın bütün palindrom olan alt sırlarını tapdıqdan sonra, özünə tapşırığı çətinləşdirmək qərarına gəldi. O, sıradakı simvolları ardıcıl olaraq hər hansı bir simvola bərabər hesab etdiyi "?" simvolu ilə əvəz edir. Məsələn, Stepan "ABA" və "A?A", "ABB" və "AB?" sırlarını bərabər hesab edir, həmçinin "AB?", "ABC??" və "?C?" sırlarını palindrom hesab edir.
Stepan hər bir simvolu "?" ilə əvəz etdikdən sonra, sıranın S palindrom olan alt sırlarının sayını müəyyən etmək istəyir (təbii ki, Stepanın öz anlayışına görə). Bundan əlavə, Stepan başlanğıc və/və ya son mövqeləri fərqli olan alt sırları fərqli hesab edir.
Stepanın hərəkətlərini avtomatlaşdıracaq bir proqram yazın ki, o, nəhayət başqa bir işlə məşğul olsun.
Giriş verilənləri
Giriş faylının ilk sətri yalnız kiçik latın hərflərindən ibarət olan S sıranı ehtiva edir. S sıranın boş olmadığı və uzunluğunun N 4000-dən çox olmadığı təmin edilir. Daha sonra 1 ilə N arasında olan N ədəd verilir - "?" ilə əvəz ediləcək simvolların nömrələri.
Sıranı S oxuduqdan sonra, onun palindrom olan alt sırlarının sayını çıxarın.
Daha sonra N dəfə aşağıdakı ardıcıllığı yerinə yetirməlisiniz:
Cari addımda sıranın "?" ilə əvəz ediləcək simvolunun nömrəsini oxuyun (1 ≤ K ≤ N).
Cari sıranın palindrom olan alt sırlarının sayını hesablayın.
Bu ədədi ayrı bir sətirdə çıxarın.
Heç bir simvolun iki dəfə "?" ilə əvəz edilməyəcəyi təmin edilir.
Çıxış verilənləri
Giriş məlumatlarında təsviri baxın.
Qeyd: "abac" sırada palindrom olan alt sırlar (1, 1), (2, 2), (3, 3), (4, 4), (1, 3). Üçüncü simvolu "?" ilə əvəz etdikdən sonra "ab?c" sırada palindrom olan alt sırlar (1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (2, 3), (3, 4). İkinci simvolu "?" ilə əvəz etdikdən sonra "a??c" sırada yalnız (1, 4) alt sıra palindrom deyil. Növbəti əvəzlərdən sonra bütün alt sırlar palindrom olacaq.