Olet labyrintissa, jossa on myös hirviöitä. Aina kun liikut askeleen, myös jokainen hirviö voi liikkua askeleen. Tavoitteesi on päästä johonkin labyrintin reunaruutuun niin, että yksikään hirviö ei ole samassa ruudussa missään vaiheessa.

Tehtäväsi on selvittää, onko tavoitteesi mahdollinen, ja jos on, tulostaa jokin reitti, jota seuraamalla pääset ulos. Suunnitelmasi täytyy toimia riippumatta siitä, miten hirviöt liikkuvat.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: labyrintin korkeus ja leveys.

Sitten syötteessä on n riviä, joista jokaisella on m merkkiä. Jokainen merkki on . (lattia), # (seinä), A (alkukohta) tai H (hirviö). Merkkejä A on tarkalleen yksi koko syötteessä.

Tuloste

Jos tavoite on mahdollinen, tulosta "10-4", ja muuten "QAQ".

Jos tavoite on mahdollinen, tulosta lisäksi esimerkki reitistä (reitin pituus ja kuvaus merkkeinä A, Y, V ja O). Voit tulostaa minkä tahansa reitin, kunhan siinä on korkeintaan n \cdot m askelta.

Rajat

• 1 \le n,m \le 1000

Esimerkki

Syöte:

5 8
########
#H..A..#
#.#.H#.#
#H#..#..
#.######

Tuloste:

10-4
5
OOAAO