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$