Leimasin

• Time limit: 1.00 s
• Memory limit: 512 MB

Haluat muodostaa merkkijonon, jonka pituus on $n$ merkkiä. Merkkijonon merkit on numeroitu $1,2,\dots,n$, ja aluksi jokainen merkki on ?.

Käytössäsi on leimasin, jonka pituus on $m$ merkkiä. Voit joka siirrolla asettaa leimasimen johonkin merkkijonon kohtaan ja korvata merkkijonon merkit tällä alueella vastaavissa kohdissa olevilla leimasimen merkeillä. Leimasimen täytyy olla kokonaan merkkijonon sisällä joka siirrolla, eikä sen asentoa voi muuttaa.

Tehtäväsi on etsiä siirtosarja, jolla voit tuottaa halutun merkkijonon leimasimen avulla, tai todeta, että tämä ei ole mahdollista.

Syöte

Ensimmäisellä rivillä on merkkijono, jossa on $n$ merkkiä: tavoitteena oleva merkkijono.

Toisella rivillä on merkkijono, jossa on $m$ merkkiä: leimasin.

Molemmat merkkijonot muodostuvat merkeistä A–Z.

Tuloste

Tulosta ensin kokonaisluku $k$: siirtojen määrä.

Tulosta sitten $k$ kokonaislukua, jotka kuvaavat siirrot järjestyksessä. Jokainen luku on välillä $1 \dots n-m+1$ ja ilmaisee leimasimen vasemman kohdan.

Voit tulostaa minkä tahansa ratkaisun, jossa $k$ on enintään $10n$. Jos mitään ratkaisua ei ole olemassa, tulosta vain luku $-1$.

Esimerkki 1

Syöte:
AABCACA
ABCA

Tuloste:
3
1 4 2

Selitys: Käytät leimasinta näin: ??????? → ABCA??? → ABCABCA → AABCACA.

Esimerkki 2

Syöte:
AYBABTU
AB

Tuloste:
-1

Osatehtävä 1 (29 pistettä)

• $1 \le m \le n \le 10$
  

Osatehtävä 2 (31 pistettä)

• $1 \le m \le n \le 100$
  

Osatehtävä 3 (40 pistettä)

• $1 \le m \le n \le 1000$