Hide

Problem C
Löggeng endanleg stöðuvél - Sammengi

Languages en is

Þú færð tvær endanlegar löggengar stöðuvélar gefnar sem samþykkja málin L1 og L2. Þú átt að prenta sammengið, endanlega löggenga stöðuvél sem samþykkir málið L=L1L2.

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 Σ=Σ1Σ2Σ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 Σj.

Hver staða er táknuð með heiltölu frá 1 til n. Gefið er að 1sn og 0fn.

Táknum fjölda staða í stöðuvélunum tveimur með n1 og n2. Þá mun inntakið uppfylla n1n2c300000.

Úttak

Prentið hvaða endanlegu löggengu stöðuvél sem er sem samþykkir sammengi 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 nc300000.

Sample Input 1 Sample Output 1
3 2 1 1
ab
1
1 2
1 3
3 3
3 2 1 1
ab
2
3 2
2 2
3 3
5 2 5 3
ab
5 2 4
1 1
2 3
2 1
4 4
2 4
Sample Input 2 Sample Output 2
1 4 1 0
acgt

1 1 1 1
1 4 1 1
acgt
1
1 1 1 1
1 4 1 1
acgt
1
1 1 1 1
Hide