Задача . H. Упоротые палиндромы

Ваша задача состоит в том, чтобы поддерживать очередь содержащую строчные буквы Латинского алфавита со следующими операциями:

• «push \(c\)»: вставить букву \(c\) в конец очереди;
• «pop»: удалить букву из начала очереди.

Изначально очередь пустая.

После каждой операции, вы должны посчитать число различных подстрок палиндромов в строке, которая получается соединением букв от начала к концу очереди.

Число различных подстрок палиндромов пустой строки равняется \(0\).

Строка \(s[1..n]\) длины \(n\) является палиндромом, если \(s[i] = s[n-i+1]\) для любого \(1 \leq i \leq n\).

Строка \(s[l..r]\) является подстрокой строки \(s[1..n]\) для любого \(1 \leq l \leq r \leq n\).

Две строки \(s[1..n]\) и \(t[1..m]\) различные, если выполняется как минимум одно из условий.

• \(n \neq m\);
• \(s[i] \neq t[i]\) для некоторого \(1 \leq i \leq \min\{n,m\}\).