تُسمى السلسلة النصية $t$ التي طولها $k$ والمكونة من أحرف صغيرة سلسلة CCPC (Character-Character-Palindrome-Character) إذا وفقط إذا تحققت الشروط التالية:

• $k \ge 4$؛
• $t_1 = t_2 = t_k$؛
• $t_3 t_4 \dots t_{k-1}$ هي سلسلة متناظرة (palindrome).

تكون السلسلة النصية التي طولها $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}$.