מחרוזת $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$), המציין את מספר הפעולות.

השורה השלישית מכילה $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}$.