Problem D
Marsi DNA

Nagu sa ilmselt tead, saab inimese DNA esitada pika stringina, kus esineb vaid neli erinevat tähte (A, C, G, T) ja iga sümbol vastab erinevale nukleotiidile (adeniin, tsütosiin, guaniin ja tümiin).

Marslastel käivad asjad aga veidi teisiti: uuringud näitavad, et viimasel NASA poolt kinni püütud marslasel on tervelt $K$ erinevat nukleotiidi! Seega saab marslase DNA esitada kui stringi, mille märgid on tähestikust suurusega $K$.

Nüüd uurib grupp teadlasi, kuidas kasutada marslaste DNA-d tehisintellektirakendustes ja neil on vaja marslase DNA näidist. Täpsemalt on nad öelnud $R$ nukleotiidi kohta, mis on minimaalne arv, kui palju vastavat nukleotiidi peab näidises olema.

Sul on vaja leida lühim võimalik nõuetele vastav DNA alamstring.

Sisend

Sisendi esimesel real on kolm täisarvu $N$, $K$ ja $R$, mis tähistavad vastavalt marslase DNA täielikku pikkust, tähestiku suurust ning nende nukleotiidide arvu, millele rakendub minimaalse arvu nõue. Kehtib reegel $1 \le R \le K \le N$.

Teisel real on $N$ tühikutega eraldatud täisarvu, mis kirjeldavad täielikku marslase DNA järjendit. $i$-s arv $D_ i$ tähistab, milline nukleotiid on marslase DNA-s $i$-ndal kohal. Nukleotiidide loendamine algab nullist, s.t $0 \leq D_ i < K$. Iga nukleotiidi esineb vähemalt üks kord.

Järgmistel $R$ real on igaühel kaks täisarvu $B$ ja $Q$, mis tähistavad nukleotiidi ja selle minimaalset soovitud hulka ($0 \le B < K, 1 \le Q \le N$). Ükski nukleotiid ei esine rohkem kui üks kord.

Väljund

Väljastada üks täisarv, lühima nõuetele vastava DNA alamstringi pikkus. Kui sellist alamstringi pole, väljastada “impossible”.

Piirangud

Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.

Näidete selgitus

Esimeses näites leidub kolm alamstringi pikkusega $2$, mis kõik sisaldavad ühe nukleotiidi 0 ja ühe 1 (täpsemalt “0 1”, “1 0” ja “0 1”), aga ei leidu ühtki alamstringi pikkusega $1$. Lühim pikkus on seega $2$.

Teises näites on (ainus) optimaalne alamstring “1 3 2 0 1 2 0”.

Kolmandas näites pole piisavalt 0-tüüpi nukleotiide.

5 2 2
0 1 1 0 1
0 1
1 1

2

13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

7

5 3 1
1 2 0 1 2
0 2

impossible