Strengur $t$ af lengd $k$ sem samanstendur af lágstöfum kallast CCPC-strengur (Character-Character-Palindrome-Character) ef og aðeins ef eftirfarandi skilyrði eru uppfyllt:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ er samhverfur strengur (palindrome).

Strengur af lengd $m$ er samhverfur ef og aðeins ef fyrir öll $1 \le i \le m$ gildir að $i$-ti stafur strengsins er sá sami og $(m - i + 1)$-ti stafur strengsins.

Til dæmis eru ccpc, ppap, zzzz og aabcddcba CCPC-strengir, en jinan, aaa og oovoo eru það ekki.

Hlutsstreng strengs $s$ má tákna með tvennd heiltalna $(l, r)$ sem uppfyllir $1 \le l \le r \le |s|$, sem samsvarar strengnum $s_l s_{l+1} \dots s_r$. Tveir hlutstrengir teljast ólíkir ef og aðeins ef vísatvenndirnar $(l, r)$ sem valdar voru eru ekki þær sömu. Gefinn er strengur $s$ sem samanstendur af lágstöfum; reiknaðu fyrst fjölda CCPC-hlutstrengja í $s$. Síðan eru framkvæmdar $n$ aðgerðir, þar sem hver aðgerð bætir lágstaf við vinstra eða hægra megin við $s$. Þú þarft að ákvarða fjölda CCPC-hlutstrengja í $s$ eftir hverja viðbót.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 100$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan streng $s$ ($4 \le |s| \le 5 \times 10^5$) sem samanstendur af lágstöfum og táknar upphaflega strenginn.

Önnur línan inniheldur heiltölu $n$ ($1 \le n \le 5 \times 10^5$), sem gefur til kynna fjölda aðgerða.

Þriðja línan inniheldur $n$ strengi af lengd $2$, $c_1, c_2, \dots, c_n$, aðskilda með bilum, sem tákna aðgerðirnar í tímaröð. Fyrir hvern streng $c_i$ er fyrri stafurinn annaðhvort L eða R, sem gefur til kynna að bætt sé við vinstra eða hægra megin við $s$, í sömu röð, og seinni stafurinn er lágstafur sem gefur til kynna stafinn sem á að bæta við.

Tryggt er að hvorki summa $|s|$ né summa $n$ yfir öll prófunartilvik fari yfir $5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $n + 1$ heiltölur aðskildar með bilum. Fyrsta heiltalan táknar svarið fyrir upphaflega strenginn og $(i + 1)$-ta heiltalan ($1 \le i \le n$) táknar svarið eftir fyrstu $i$ aðgerðirnar.

Dæmi

Inntak

2
iloveccpc
6
Rj Ri Ln La Ln Ln
cpcpccp
9
Lc Lc Rp Rc Lc Lc Rp Rp Rc

Úttak

1 1 1 1 1 1 2
0 2 3 3 4 5 7 8 8 9

Athugasemd

Fyrir annað prófunartilvikið verður $s$ að cccccpcpccppcppc eftir allar aðgerðirnar. CCPC-hlutstrengir hans eru: $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}$.