Problem G
Marsiešu DNS

Cilvēku DNS var reprezentēt kā simbolu virkni, izmantojot četrus alfabēta burtus (A, C, G, T), kur katrs simbols reprezentē atšķirīgus nukleotīdus (attiecīgi – adenīns, citozīns, guanīns, timīns).

Marsiešiem, savukārt, DNS uzbūve ir citāda. Pētījums, kas tika veikts uz marsiešiem, kurus nesen noķēra NASA, atklāja, ka marsiešu DNS sastāv no $K$ atšķirīgiem nukleotīdiem! Tādējādi marsiešu DNS var reprezentēt kā simbolu virkni, ko veido izmantojot $K$ burtu alfabētu.

Pašlaik pētnieku grupa ir ieinteresēta pielietot marsiešu DNS mākslīgā intelekta izveidē. Pētnieki ir pieprasījuši pēc kārtas sekojošu simbolu apakšvirkni no marsiešu DNS simbolu virknes. Pētnieki $R$ nukleotīdiem ir norādījuši minimālo daudzumu – cik reižu vismaz attiecīgajam nukleotīdam ir jāparādās pieprasītajā paraugā.

Jūs esat ieinteresēts atrast īsāko pēc kārtas sekojošo simbolu apakšvirkni no DNS, kas apmierina pētnieku prasības.

Ievaddati

Pirmā rinda satur trīs veselus skaitļus $N$, $K$ un $R$ – kopējais marsieša DNS garums, alfabēta izmērs un nukleotīdu skaits, kam pētnieki ir norādījuši minimālā daudzuma prasību – $1 \le R \le K \le N$.

Otrā rinda satur $N$ veselus skaitļus, kas atdalīti ar tukšumzīmi, – marsiešu DNS simbolu virkne. Virknes $i$-tais skaitlis, $D_ i$, norāda, kurš nukleotīds ir $i$-tajā pozīcijā DNS simbolu virknē. Nukleotīdi ir numurēti sākot ar $0$, t.i. $0 \leq D_ i < K$. Katrs nukleotīds DNS simbolu virknē parādīsies vismaz vienu reizi.

Sekojošās $R$ rindas katra satur divus veselus skaitļus $B$ un $Q$ – nukleotīds un tā pieprasītais minimālais daudzums. Attiecīgi ($0 \le B < K, 1 \le Q \le N$). Neviens nukleotīds nebūs minēts vairāk kā vienu reizi šajās $R$ rindās.

Izvaddati

Izvadiet vienu veselu skaitli – garumu īsākajai pēc kārtas sekojošu simbolu apakšvirknei no DNS, kas apmierina pētnieku prasības. Ja šāda apakšvirkne neeksistē, izvadiet “impossible”.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

Paraugu paskaidrojumi

Pirmajā paraugā ir trīs pēc kārtas sekojošu simbolu apakšvirknes ar garumu $2$, kas satur pa vienam 0 un 1 nukleotīdam (tās ir “0 1”, “1 0” un “0 1”), bet nav nevienas apakšvirknes ar garumu $1$. Tādēļ īsākais garums ir $2$.

Otrajā paraugā (unikāla) optimālā pēc kārtas sekojošu simbolu apakšvirkne ir “1 3 2 0 1 2 0”.

Trešajā paraugā nav pietiekams skaits ar 0 tipa nukleotīdiem.

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