Строка $t$ длины $k$, состоящая из строчных латинских букв, называется строкой CCPC (Character-Character-Palindrome-Character) тогда и только тогда, когда выполняются следующие условия:
- $k \ge 4$;
- $t_1 = t_2 = t_k$;
- $t_3 t_4 \dots t_{k-1}$ является палиндромом.
Строка длины $m$ является палиндромом тогда и только тогда, когда для всех $1 \le i \le m$ её $i$-й символ равен её $(m - i + 1)$-му символу.
Например, ccpc, ppap, zzzz и aabcddcba являются строками CCPC, а jinan, aaa и oovoo — нет.
Подстроку строки $s$ можно представить парой целых чисел $(l, r)$, удовлетворяющих условию $1 \le l \le r \le |s|$, что соответствует строке $s_l s_{l+1} \dots s_r$. Две подстроки считаются различными тогда и только тогда, когда выбранные пары индексов $(l, r)$ не совпадают. Дана строка $s$, состоящая из строчных букв; сначала вычислите количество подстрок CCPC в $s$. Затем выполняется $n$ операций, каждая из которых вставляет строчную букву слева или справа от $s$. Вам необходимо определить количество подстрок CCPC в $s$ после каждой вставки.
Входные данные
Первая строка содержит целое число $T$ ($1 \le T \le 100$) — количество наборов входных данных.
Для каждого набора входных данных первая строка содержит строку $s$ ($4 \le |s| \le 5 \times 10^5$), состоящую из строчных букв и представляющую начальную строку.
Вторая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^5$) — количество операций.
Третья строка содержит $n$ строк длины $2$: $c_1, c_2, \dots, c_n$, разделённых пробелами, которые описывают операции в хронологическом порядке. Для каждой строки $c_i$ первый символ равен L или R, указывая, что вставка происходит слева или справа от $s$ соответственно, а второй символ — строчная буква, указывающая вставляемый символ.
Гарантируется, что ни сумма $|s|$, ни сумма $n$ по всем наборам входных данных не превышают $5 \times 10^5$.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую $n + 1$ целых чисел, разделённых пробелами. Первое целое число обозначает ответ для начальной строки, а $(i + 1)$-е целое число ($1 \le i \le n$) обозначает ответ после первых $i$ операций.
Пример
Входные данные
2 iloveccpc 6 Rj Ri Ln La Ln Ln cpcpccp 9 Lc Lc Rp Rc Lc Lc Rp Rp Rc
Выходные данные
1 1 1 1 1 1 2 0 2 3 3 4 5 7 8 8 9
Примечание
Во втором наборе входных данных после всех операций строка $s$ принимает вид cccccpcpccppcppc. Её подстроки CCPC включают: $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}$.