Justiina ja Kotivalo ovat n \times m -kokoisessa sokkelossa. Sokkelossa voi liikkua lattiaruutuja pitkin pysty- ja vaakasuunnassa. Samassa ruudussa voi olla enintään yksi henkilö.

Kahden ruudun välinen etäisyys on Manhattan-etäisyys, eli kun ruudut ovat (y_1,x_1) ja (y_2,x_2), niiden etäisyys on |y_1-y_2|+|x_1-x_2|.

Tehtäväsi on selvittää, kuinka lähelle toisiaan Justiina ja Kotivalo voivat päästä, jos he liikkuvat optimaalisesti.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: sokkelon korkeus ja leveys.

Tämän jälkeen tulee sokkelon kuvaus: n riviä, joista jokaisella on m merkkiä. Merkki voi olla . (lattia), # (seinä), A (Justiinan alkukohta) tai B (Kotivalon alkukohta).

Voit olettaa, että jokainen reunaruutu on seinää ja merkkejä A ja B on molempia tasan yksi syötteessä.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen etäisyys.

Esimerkki 1

Syöte:

5 8
########
#A#.#.B#
#.#.####
#...#..#
########

Tuloste:

2

Esimerkki 2

Syöte:

5 8
########
#A#...B#
#.#.####
#...#..#
########

Tuloste:

1

Osatehtävä 1 (28 pistettä)

• 3 \le n,m \le 20

Osatehtävä 2 (72 pistettä)

• 3 \le n,m \le 1000