Pienistä kirjaimista koostuvaa pituuden $k$ merkkijonoa $t$ kutsutaan CCPC-merkkijonoksi (Character-Character-Palindrome-Character)jos ja vain jos seuraavat ehdot täyttyvät:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ on palindromi.

Pituuden $m$ merkkijono on palindromi jos ja vain jos kaikilla $1 \le i \le m$ merkkijonon $i$-s merkki on sama kuin merkkijonon $(m - i + 1)$-s merkki.

Esimerkiksi ccpc, ppap, zzzz ja aabcddcba ovat CCPC-merkkijonoja, kun taas jinan, aaa ja oovoo eivät ole.

Merkkijonon $s$ osamerkkijono voidaan esittää kokonaislukuparina $(l, r)$, joka toteuttaa ehdon $1 \le l \le r \le |s|$ ja vastaa merkkijonoa $s_l s_{l+1} \dots s_r$. Kahta osamerkkijonoa pidetään erisuurina jos ja vain jos valitut indeksiparit $(l, r)$ eivät ole samat. Annettuna pienistä kirjaimista koostuva merkkijono $s$, laske ensin CCPC-osamerkkijonojen lukumäärä merkkijonossa $s$. Tämän jälkeen suoritetaan $n$ operaatiota, joista jokainen lisää pienen kirjaimen merkkijonon $s$ vasemmalle tai oikealle puolelle. Sinun tulee määrittää CCPC-osamerkkijonojen lukumäärä merkkijonossa $s$ jokaisen lisäyksen jälkeen.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää pienistä kirjaimista koostuvan merkkijonon $s$ ($4 \le |s| \le 5 \times 10^5$), joka kuvaa alkuperäistä merkkijonoa.

Toinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 5 \times 10^5$), joka ilmaisee operaatioiden lukumäärän.

Kolmas rivi sisältää $n$ pituuden $2$ merkkijonoa $c_1, c_2, \dots, c_n$ välilyönnein erotettuina, jotka kuvaavat operaatiot aikajärjestyksessä. Jokaisessa merkkijonossa $c_i$ ensimmäinen merkki on joko L tai R, mikä ilmaisee lisäyksen tapahtuvan vastaavasti merkkijonon $s$ vasemmalle tai oikealle puolelle, ja toinen merkki on pieni kirjain, joka ilmaisee lisättävän merkin.

On taattu, että $|s|$:n summa ja $n$:n summa kaikkien testitapausten yli eivät kumpikaan ylitä arvoa $5 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n + 1$ kokonaislukua välilyönnein erotettuina. Ensimmäinen kokonaisluku kuvaa vastausta alkuperäiselle merkkijonolle, ja $(i + 1)$-s kokonaisluku ($1 \le i \le n$) kuvaa vastausta ensimmäisen $i$ operaation jälkeen.

Esimerkki

Syöte

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

Tuloste

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

Huomautus

Toisessa testitapauksessa kaikkien operaatioiden jälkeen merkkijonoksi $s$ tulee cccccpcpccppcppc. Sen CCPC-osamerkkijonoja ovat: $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}$.