Uolevi on salannut tutkimuspöytäkirjansa. Hänellä on paperilapulla salausavain, joka kertoo jokaiselle kirjaimelle, miksi kirjaimeksi se salauksessa muutetaan. Mitään kahta eri kirjainta ei salata samalle kirjaimelle, joten salaus voidaan purkaa käyttämällä salausavainta toiseen suuntaan.

Uolevi kuitenkin epähuomiossa heitti salausavaimen silppuriin, joten nyt hänen täytyy murtaa salaus. Hätä ei ole kuitenkaan tämän näköinen, sillä hän muistaa erään tutkimuspöytäkirjassaan esiintyvän kohdan ulkoa, joten sen avulla hän voisi selvittää ainakin osan salausavaimesta.

Uolevi ei kuitenkaan muista, missä kohtaa tutkimuspöytäkirjaa hänen muistamansa teksti on. Tehtävänäsi on etsiä kohta tutkimuspöytäkirjasta jossa teksti voi esiintyä.

Syöte

Syötteen ensimmäisellä rivillä on Uolevin tutkimuspöytäkirja salattuna. Toisella rivillä on Uolevin muistama teksti tutkimuspöytäkirjasta salaamattomana.

Tuloste

Tulosta ensimmäinen kohta tutkimuspöytäkirjaa, jossa Uolevin muistama teksti voi alkaa. Numerointi aloitetaan ykkösestä.

Mikäli tällaista kohtaa ei ole, tulosta QAQ.

Rajat

Tekstien pituudet ovat välillä 1\ldots 5 \cdot 10^5.

Tekstit koostuvat kirjaimista A\ldotsZ.

Tehtävän aikaraja on poikkeuksellisesti 7 sekuntia.

Esimerkki

Syöte:

AYBABTU
LOL

Tuloste:

3