Une chaîne de caractères $t$ de longueur $k$ composée de lettres minuscules est appelée une chaîne CCPC (Character-Character-Palindrome-Character) si et seulement si les conditions suivantes sont remplies :
- $k \ge 4$ ;
- $t_1 = t_2 = t_k$ ;
- $t_3 t_4 \dots t_{k-1}$ est un palindrome.
Une chaîne de longueur $m$ est un palindrome si et seulement si pour tout $1 \le i \le m$, le $i$-ème caractère de la chaîne est égal au $(m - i + 1)$-ème caractère de la chaîne.
Par exemple, ccpc, ppap, zzzz et aabcddcba sont des chaînes CCPC, tandis que jinan, aaa et oovoo ne le sont pas.
Une sous-chaîne d'une chaîne $s$ peut être représentée par un couple d'entiers $(l, r)$ vérifiant $1 \le l \le r \le |s|$, correspondant à la chaîne $s_l s_{l+1} \dots s_r$. Deux sous-chaînes sont considérées comme différentes si et seulement si les couples d'indices $(l, r)$ choisis ne sont pas les mêmes. Étant donné une chaîne $s$ composée de lettres minuscules, calculez d'abord le nombre de sous-chaînes CCPC dans $s$. Ensuite, $n$ opérations sont appliquées, chacune insérant une lettre minuscule à gauche ou à droite de $s$. Vous devez déterminer le nombre de sous-chaînes CCPC dans $s$ après chaque insertion.
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 100$), indiquant le nombre de cas de test.
Pour chaque cas de test, la première ligne contient une chaîne $s$ ($4 \le |s| \le 5 \times 10^5$) composée de lettres minuscules, représentant la chaîne initiale.
La deuxième ligne contient un entier $n$ ($1 \le n \le 5 \times 10^5$), indiquant le nombre d'opérations.
La troisième ligne contient $n$ chaînes de longueur $2$, $c_1, c_2, \dots, c_n$, séparées par des espaces, représentant les opérations dans l'ordre chronologique. Pour chaque chaîne $c_i$, le premier caractère est soit L soit R, indiquant que l'insertion se fait respectivement à gauche ou à droite de $s$, et le second caractère est une lettre minuscule indiquant le caractère à insérer.
Il est garanti que ni la somme de $|s|$ ni la somme de $n$ sur l'ensemble des cas de test ne dépassent $5 \times 10^5$.
Sortie
Pour chaque cas de test, affichez une seule ligne contenant $n + 1$ entiers séparés par des espaces. Le premier entier représente la réponse pour la chaîne initiale, et le $(i + 1)$-ème entier ($1 \le i \le n$) représente la réponse après les $i$ premières opérations.
Exemple
Entrée
2 iloveccpc 6 Rj Ri Ln La Ln Ln cpcpccp 9 Lc Lc Rp Rc Lc Lc Rp Rp Rc
Sortie
1 1 1 1 1 1 2 0 2 3 3 4 5 7 8 8 9
Note
Pour le deuxième cas de test, après toutes les opérations, $s$ devient cccccpcpccppcppc. Ses sous-chaînes CCPC comprennent : $s_{1\dots4} = \text{cccc}$, $s_{1\dots5} = \text{ccccc}$, $s_{2\dots5} = \text{cccc}$, $s_{3\dots10} = \text{cccpcpcc}$, $s_{4\dots7} = \text{ccpc}$, $s_{4\dots9} = \text{ccpcpc}$, $s_{9\dots13} = \text{ccppc}$, $s_{9\dots16} = \text{ccppcppc}$, $s_{11\dots14} = \text{ppcp}$.