Problem H
Löggeng endanleg stöðuvél - Kleene stjarna

Þú færð endanlega löggenga stöðuvél gefna sem samþykkir málið $\mathcal{L}$. Þú átt að prenta Kleene stjörnuna, endanlega löggenga stöðuvél sem samþykkir málið $\mathcal{L}^{\ast }$.

Inntak

Fyrsta lína inntaksins 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 $\Sigma = \Sigma _1 \Sigma _2 \dots \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 $\Sigma _j$.

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

Úttak

Prentið hvaða endanlega löggengu stöðuvél sem er sem samþykkir Kleene stjörnu málsins sem inntaksstöðuvélin samþykkir. Ú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 \leq 300\, 000$.

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

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

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

1 4 1 1
acgt
1
1 1 1 1

1 4 1 1
acgt
1
1 1 1 1