V jeden zimný deň si Buj povedal, že bude lenivé prasa. Namiesto toho, aby šiel poctivo do školy, vybral sa do supermarketu, nakúpil neskutočne veľa čokolády, a potom ju zvyšok dňa konzumoval.

V ten deň zadal pán profesor algebry domácu úlohu. Buj sa o nej síce dozvedel z internetovej stránky predmetu, ale keďže na hodine nebol, netuší, ako ju má riešiť. Pomôžte mu!

Úloha

V tejto úlohe budeme pracovať s kompletne uzátvorkovanými výrazmi. Tie si definujeme takto:

• Reťazec $a$ (jedno konkrétne písmeno a) je kompletne uzátvorkovaný výraz.

• Ak $A$ a $B$ sú kompletne uzátvorkované výrazy, tak aj $(A + B)$ je kompletne uzátvorkovaný výraz.

• Nič, čo sa nedá vyskladať postupným použitím dvoch predchádzajúcich pravidiel, nie je kompletne uzátvorkovaný výraz.

Podľa tejto definície sú kompletne uzátvorkované výrazy napríklad $a$, $(a+a)$, $((a+a)+a)$ a $(((a + a) + (a + a)) + ((a + a) + (a + a)))$. Vonkajšie zátvorky vo výrazoch vynechávame. Napríklad, namiesto $(a+(a+a))$ píšeme $a+(a+a)$.

Na vstupe dostanete dva kompletne uzátvorkované výrazy. O nich chceme dokázať, že sa rovnajú. Môžeme pritom použiť iba asociatívny zákon, ktorý hovorí, že $A+(B+C) = (A+B)+C$. V podstate teda chceme previesť prvý výraz na druhý, pričom sú povolené len dve operácie:

• Ak v našom výraze máme podvýraz tvaru $(A+B)+C$, tak ho môžeme prepísať na $A+(B+C)$. Napríklad výraz $$a + ((\, \overbrace{(a + a)}^{A} + \overbrace{\vphantom{(}a}^{B}) + \overbrace{(a + a)}^{C}\,)$$ môžeme prepísať na $$a + (\, \overbrace{(a + a)}^{A} + (\overbrace{\vphantom{(}a}^{B} + \overbrace{(a + a)}^{C}\,)) \text{.}$$ Tejto operácii budeme hovoriť rotácia doprava.

• Prepísaniu opačným smerom, teda nahradenie podvýrazu tvaru $A+(B+C)$ výrazom $(A+B)+C$, budeme hovoriť rotácia doľava.

Vašou úlohou je nájsť postupnosť rotácii, ktorou prevedieme prvý výraz na druhý.

Formát vstupu

Na prvom riadku vstupu je kladné číslo $t$: počet testov. Nasledujú popisy jednotlivých testov. Každý test začína prázdnym riadkom, za ktorým nasledujú dva riadky obsahujúce jednotlivé výrazy. Môžete predpokladať, že oba výrazy majú rovnakú dĺžku, $n$.

Je osem sád testovacích vstupov, obmedzenia pre jednotlivé sady sú nasledovné:

Formát výstupu

Pre každý test vypíšte postupnosť rotácii, ktorou prevedieme prvý výraz na druhý, v nasledujúcom formáte. Na prvom riadku nech je dĺžka postupnosti, $k$, a na nasledujúcich $k$ riadkoch nech sú popisy jednotlivých rotácii v poradí, v akom ich vykonáme.

Očíslujme si znaky $+$ v našom výraze zľava doprava $1, 2, \ldots$, teda ak by sme z výrazu vynechali zátvorky, dostali by sme

$$a +_1 a +_2 a +_3 a +_4 \ldots$$

Rotáciu doprava z $(A +_i B) +_j C$ na $A +_i (B +_j C)$ zapíšeme ako riadok “$j$ R”. Podobne, rotáciu doľava z $A +_i (B +_j C)$ zapíšeme ako “$i$ L”.

Príklady

Input:

2

a+(a+(a+a))
((a+a)+a)+a

(a+a)+(a+a)
a+((a+a)+a)

Output:

2
1 L
2 L
3
2 L
2 R
3 R

Prvý postup: $$a+(a+(a+a))\ \rightarrow\ (a+a)+(a+a)\ \rightarrow\ ((a+a)+a)+a$$ Druhý postup: $$(a+a)+(a+a)\ \rightarrow\ ((a+a)+a)+a\ \rightarrow\ (a+(a+a))+a\ \rightarrow\ a+((a+a)+a)$$ Všimnite si, že druhý test sa dá vyriešiť aj na dve rotácie. Nám však stačí vypísať ľubovoľný funkčný postup.