Problem G
Löggeng endanleg stöðuvél - Samskeyting

Þú færð tvær endanlegar löggengar stöðuvélar gefnar sem samþykkja málin ${\mathcal{L}}_1$ og ${\mathcal{L}}_2$. Þú átt að prenta samskeytinguna, endanlega löggenga stöðuvél sem samþykkir málið $\mathcal{L}={\mathcal{L}}_1{\mathcal{L}}_2$.

Inntak

Inntakið inniheldur lýsingu á tveimur endanlegum löggengum stöðuvélum með sama stafróf. Hverri þeirra er lýst sem fylgir.

Fyrsta línan inniheldur fjórar jákvæðar heiltölur $n$, $c$, $s$ og $f$ þar sem $n$ er fjöldi staða, $c$ er stærð stafrófsins, $s$ er upphafsstaðan og $f$ er fjöldi lokastaða. Önnur línan inniheldur streng $\mathrm{\Sigma }={\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2\dots {\mathrm{\Sigma }}_c$ sem samanstendur af $c$ ólíkum táknum sem eru allt ASCII lágstafir. Þriðja línan inniheldur $f$ ólíkar jákvæðar heiltölur, mengi lokastaða stöðuvélarinnar. Næst fylgja $n$ línur, hver með $c$ jákvæðum heiltölum, sem gefa stöðuskiptatöfluna. Sem sagt, $j$-ta talan á $i$-tu línu gefur stöðuna sem stöðuvélin fer í ef hún var í stöðu $i$ og las inn stafinn ${\mathrm{\Sigma }}_j$.

Hver staða er táknuð með heiltölu frá $1$ til $n$. Gefið er að $1\le s\le n$ og $0\le f\le n$.

Einnig er gefið að fjöldi staða í stöðuvélunum tveimur samanlagður sé mest $21$.

Úttak

Prentið hvaða endanlegu löggengu stöðuvél sem er sem samþykkir samskeytingu mála inntaksvélanna. Úttak þitt á að vera á sama formi og inntakið og á að uppfylla sömu takmörkunum og inntakið, nema hún má vera stærri. Hún þarf að uppfylla $n\cdot c\le 300000$.

Þú mátt gera ráð fyrir að til sé brigðgeng endanleg stöðuvél sem samþykkir $\mathcal{L}$ sem má breyta í löggenga endanlega stöðuvél með veldismengjaaðferð sem uppfyllir úttaksskilyðrin án frekari breytinga.

2 2 1 1
ab
1
1 2
2 2
3 2 1 1
ab
2
3 2
3 2
3 3

5 2 1 2
ab
3 4
2 3
2 4
5 3
5 4
5 5

1 4 1 0
acgt

1 1 1 1
1 4 1 1
acgt
1
1 1 1 1

1 4 1 0
acgt

1 1 1 1