Problem E
Hackenbush purpuraviður

Sýniinntak 2

Hackenbush er leikur með leggjum af þremur litum sem tengjast í hvorn annan eða jörð. Leggirnir eru allir rauðir, bláir eða grænir. Annar leikmaður getur hoggið rauða og græna leggi og hinn leikmaðurinn bláa og græna leggi. Þegar leikmaður heggur legg er honum eytt út. Einnig er öllum leggjum sem hafa ekki leið niður í jörð um aðra leggi eytt út.

Gildi Hackenbush leiks með rauðum og bláum leggjum er skilgreint í nokkrum skrefum. Við segjum að stakur blár leggur sé $+1$, stakur rauður leggur sé $-1$. Eins segjum við að staða þar sem sá sem leikur fyrst tapar ávallt hafi gildi $0$. Með því að bera saman stöður og fá hvenær summan er núll getum við þá fundið gildi nýrra staða. Tökum sem dæmi bláan legg fest við rauðan legg sem er fest í jörð. Ef við tökum tvö eintök af þeirri stöðu og svo einn stakann bláann legg fæst staða sem hefur gildið $0$. Þar með er gildi stöðunnar sem við erum að skoða $-1/2$.

Þú færð gefna stöðu af Hackenbush purpuravið. Þetta er staða í leiknum Hackenbush þar sem allir leggir eru bláir eða rauðir og engin rás er í stöðunni.

Þú þarft að ákvarða gildi leiksins. Sýna má að þetta er ávallt heiltölubrot.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $0 \leq n \leq 10^5$, fjöldi leggja. Næsta lína inniheldur $n$ heiltölur $-1 \leq e_i \leq n$, $e_i \neq 0$. Talan $e_i$ gefur hvaða leggur er beint fyrir neðan legg $i$ á leiðinni niður að jörðu. Ef $e_i = -1$ snertir leggur $i$ jörðina. Gefið er að $e_i$ vísi ávallt í legg sem hefur þegar komið fyrir í inntaki, nema þegar $e_i = -1$. Loks er gefin lína með streng af $n$ stöfum, þar sem hver stafur er R eða B. Ef $i$-ti stafurinn er R þá er $i$-ti leggurinn rauður, annars er hann blár. Enginn leggur er meir en $10^3$ leggjum frá jörðu.

Úttak

Ef gildi leiksins er $p/2^q$ prentið p/2q þar sem $p/2^q$ er fullstytt brot. Ef brotið er heiltala, prentið gildið án /20. Gildi leiksins er ávallt á þessu formi.

12
-1 1 2 3 3 5 5 7 -1 -1 10 10
BRBBRBBRRBRR

5/2^6

39
-1 1 2 3 4 4 4 7 7 9 9 1 12 13 13 15 16 16 18 18 15 21 21 12 24 25 25 24 28 28 24 31 12 33 34 34 2 37 37
BRRRBBRRBBRRRBBRRBRRBBBRBRRBRRBRRBRRRBR

65/2^12