Hide

Problem M
Löggeng endanleg stöðuvél - Talning

Languages en is

Þú færð endanlega löggenga stöðuvél gefna sem samþykkir málið L. Þú færð svo fyrirspurnir sem biðja um fjölda orða af tiltekinni lengd í L, sem þú skalt prenta í sömu röð og fyrirspurnir eru gefnar.

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 Σ=Σ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ð nc2000, 1sn og 0fn.

Að lokum kemur heiltala m, þar sem 1m10000 og svo m línur. Lína i inniheldur heiltöluna i, fyrir öll 1im, sem táknar fyrirspurn um fjölda orða af lengd i í L. Þú mátt gera ráð fyrir að in500000 fyrir sérhvert i.

Úttak

Fyrir sérhverja fyrirspurn skaltu prenta fjölda orða með tilteknu lengdina í L. Þar sem þessar tölur geta verið mjög stórar skaltu skrifa þær út mátaðar við 1000000007.

Sample Input 1 Sample Output 1
5 2 1 2
ab
4 5
2 3
3 4
4 5
5 4
4 4
5
0
1
2
3
4
0
0
3
8
16
Sample Input 2 Sample Output 2
2 4 1 1
acgt
1
2 2 2 2
2 2 2 2
3
0
1
2
1
0
0
Hide