H. Palindrome Addictstime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYour task is to maintain a queue consisting of lowercase English letters as follows:   "push c": insert a letter c at the back of the queue;  "pop": delete a letter from the front of the queue. Initially, the queue is empty. After each operation, you are asked to count the number of distinct palindromic substrings in the string that are obtained by concatenating the letters from the front to the back of the queue.Especially, the number of distinct palindromic substrings of the empty string is 0. A string s[1..n] of length n is palindromic if s[i] = s[n-i+1] for every 1 \leq i \leq n. The string s[l..r] is a substring of string s[1..n] for every 1 \leq l \leq r \leq n. Two strings s[1..n] and t[1..m] are distinct, if at least one of the following holds.   n \neq m;  s[i] \neq t[i] for some 1 \leq i \leq \min\{n,m\}. InputThe first line is an integer q (1 \leq q \leq 10^6), indicating the number of operations.Then q lines follow. Each of the following lines contains one of the operations as follows.   "push c": insert a letter c at the back of the queue, where c is a lowercase English letter;  "pop": delete a letter from the front of the queue. It is guaranteed that no "pop" operation will be performed when the queue is empty.OutputAfter each operation, print the number of distinct palindromic substrings in the string presented in the queue. ExampleInput
12
push a
pop
push a
push a
push b
push b
push a
push a
pop
pop
pop
push b
Output
1
0
1
2
3
4
5
6
5
4
3
4
NoteLet s_k be the string presented in the queue after the k-th operation, and let c_k be the number of distinct palindromic substrings of s_k. The following table shows the details of the example. ks_kc_k1a12\textsf{empty}03a14aa25aab36aabb47aabba58aabbaa69abbaa510bbaa411baa312baab4 It is worth pointing out that   After the 2-nd operation, the string is empty and thus has no substrings. So the answer is 0;  After the 8-th operation, the string is "aabbaa". The 6 distinct palindromic substrings are "a", "aa", "aabbaa", "abba", "b", and "bb". 
12
push a
pop
push a
push a
push b
push b
push a
push a
pop
pop
pop
push b

1 0 1 2 3 4 5 6 5 4 3 4 
['data structures', 'strings', '*3300']