สตริง $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$) แทนจำนวนการดำเนินการ

บรรทัดที่สามประกอบด้วยสตริงความยาว $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}$