verone

Miriapodul Verone trăieşte cel mult $12$ luni, dar nu este nefericit, întrucât viaţa i se pare lungă şi frumoasă. I se spune Verone deoarece corpul său cilindric este alcătuit din segmente colorate, iar fiecare segment poate avea doar una dintre culorile: verde, roşu sau negru.

În prima lună de viaţă, corpul miriapodului este format dintr-un singur segment. În fiecare dintre lunile următoare, fiecare segment $s$ creşte în lungime şi se divide în trei segmente: $s1, s2$ şi $s3$. Segmentele $s1$ şi $s3$ păstrează culoarea segmentului $s$, în vreme ce segmentul $s2$, cel din mijloc, se colorează astfel: dacă $s$ era verde, atunci $s2$ devine roşu. Dacă $s$ era roşu, atunci $s2$ devine negru. Dacă $s$ era negru, atunci $s2$ devine verde.

Cineva a găsit un fragment dintr-un asemenea miriapod, rezultat în urma unei lupte fatale pentru miriapod, cu o altă vieţuitoare.

Cerinţă

Cunoscând culoarea unicului segment în prima lună de viaţă a miriapodului şi succesiunea de culori a fragmentului găsit, scrieţi un program care determină vârsta acestuia şi succesiunea de culori a tuturor segmentelor sale înainte de începerea luptei

Date de intrare

Pe prima linie a fişierului verone.in se află un singur caracter $c$, reprezentând culoarea unicului segment din care era format miriapodul în prima lună de viaţă. Valorile posibile pentru $c$ sunt V, R sau N. Pe linia a doua se găseşte un şir de caractere reprezentând culorile segmentelor fragmentului găsit. Fiecare caracter al şirului este unul dintre caracterele V, R sau N.

Date de ieșire

Pe prima linie a fişierului verone.out, se va scrie un număr natural $v$, reprezentând vârsta miriapodului în momentul luptei, exprimată în luni calendaristice. Pe linia a doua se va scrie o succesiune de caractere, reprezentând culorile tuturor segmentelor miriapodului Verone în momentul în care acesta avea vârsta $v$.

Restricții și precizări

• $2 \leq$ lungimea fragmentului $\leq 40 \ 000$;
• Caracterele de pe linia a doua a fişierului de intrare nu sunt despărţite prin spaţii;
• Dacă există mai multe soluţii posibile, atunci se consideră aceea corespunzătoare vârstei minime;
• Pentru determinarea corectă a valorii $v$, se acordă $40\%$ din punctajul total.

Exemplul 1

verone.in

R
NR

verone.out

2
RNR

Explicație

Miriapodul a pierdut fragmentul NR în cea dea doua lună de viaţă. Culorile tuturor segmentelor sale în acel moment erau: RNR

Exemplul 2

verone.in

V
VRNRV

verone.out

3
VRVRNRVRV

Explicație

Fragmentul VRNRV a fost pierdut în cea dea treia lună. Culorile tuturor segmentelor miriapodului în acel moment erau: VRVRNRVRV