Кіші латын әріптерінен тұратын ұзындығы $k$ болатын $t$ жолы келесі шарттар орындалса және тек сонда ғана 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$ жолының ішкі жолын $1 \le l \le r \le |s|$ шартын қанағаттандыратын, $s_l s_{l+1} \dots s_r$ жолына сәйкес келетін $(l, r)$ бүтін сандар жұбымен көрсетуге болады. Екі ішкі жол таңдалған $(l, r)$ индекстер жұбы бірдей болмаған жағдайда және тек сонда ғана әртүрлі болып саналады. Кіші әріптерден тұратын $s$ жолы берілген, алдымен $s$ ішіндегі CCPC ішкі жолдарының санын есептеңіз. Содан кейін $n$ операция орындалады, олардың әрқайсысы $s$ жолының сол немесе оң жағына кіші әріпті кірістіреді. Әр кірістіруден кейін $s$ ішіндегі CCPC ішкі жолдарының санын анықтауыңыз керек.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін $T$ ($1 \le T \le 100$) бүтін саны берілген.

Әрбір тест үшін бірінші жолда бастапқы жолды білдіретін, кіші әріптерден тұратын $s$ ($4 \le |s| \le 5 \times 10^5$) жолы берілген.

Екінші жолда операциялар санын білдіретін $n$ ($1 \le n \le 5 \times 10^5$) бүтін саны берілген.

Үшінші жолда хронологиялық ретпен операцияларды білдіретін, бос орындармен бөлінген ұзындығы $2$ болатын $n$ жол $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}$.