5. Lenivé prasa

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.