Ivica proučava kriptografiju, znanost koja se bavi šifriranjem i slanjem poruka u takvom obliku da ih samo onaj kome su namijenjene može pročitati. Pronašao je metodu za šifriranje koja odabranu znamenku \(Z\) pretvara u zapis (šifrat) koji se sastoji od \(K\) nula i jedinica. Prvo se odabere neki ključ. Ključ je uzlazno sortiran niz od \(K\) ne nužno različitih znamenki (npr. ako je \(K=5\) tada su „01248“, „12345“, „00122“ neki od mogućih ključeva).

Ako je znamenku \(Z\) moguće izraziti kao zbroj od X znamenki koje se pojavljuju u ključu, tada će na itom mjestu, gledajući s lijeva, u šifratu znamenke \(Z\) pisati „1“ ako je na i-tom mjestu u ključu, isto gledajući s lijeva, znamenka koja sudjeluje u zbroju. Inače na tom mjestu u šifratu piše „0“. Ako postoji više mogućih šifrata znamenke \(Z\), tada ih treba sve ispisati. Svaku znamenku iz ključa u zbroju smijete iskoristiti najviše jednom.

Npr. ako je \(Z=8\), \(K=5\), \(X=2\), a odabrani ključ „01236“, tada je traženi šifrat oblika „00101“ jer se 8 može izraziti kao zbroj dvije znamenke iz ključa na samo jedan način (2+6=8, „01236“ -> „00101“). Napiši program koji za zadanu znamenku \(Z\), brojeve \(K\) i \(X\) te ključ duljine \(K\) određuje i ispisuje šifrat (ili šifrate) znamenke \(Z\) na opisani način. Zadanu znamenku uvijek će biti moguće šifrirati.

ULAZNI PODACI

• U prvom retku nalazi se prirodan broj \(K\) \((1 ≤ K ≤ 20)\), duljina ključa iz teksta zadatka.
• U drugom retku nalazi se niz od \(K\) znamenki, ključ iz teksta zadatka.
• U trećem retku nalazi se prirodan broj \(X\) \((1 ≤ X ≤ K)\) iz teksta zadatka.
• U četvrtom retku nalazi se znamenka \(Z\) \((0 ≤ Z ≤ 9)\) iz teksta zadatka.

IZLAZNI PODACI

• Traženi šifrat ili šifrati znamenke \(Z\), svaki u svom retku. Redoslijed ispisa nije bitan.

BODOVANJE

• U skupu test primjera vrijednim->a<< 65 bodova vrijedit će da je \(X ≤ 3\).
• U skupu test primjera vrijednima 30 bodova postojat će samo jedan mogući šifrat znamenke \(Z\).

PRIMJERI TEST PODATAKA

ulaz

5
01247
2
5

izlaz

01010

Opis prvog test podatka:

"01247" -> 1+4=5 -> 01010

ulaz

6
001234
3
6

izlaz

100101
010101
001110

Opis drugog test podatka:

„001234“ -> 0+2+4 -> 100101; „001234“-> 0+2+4 -> 010101; „001234“-> 1+2+3 -> 001110;

ulaz

5
01236
2
8

izlaz

00101