Qapaq

Petya Pyatoçkin dərs zamanı darıxarkən özünə bir oyun tapdı. O, dəftərdən cırılmış düzbucaqlı bir vərəqin bəzi hüceyrələrini qələmlə qaraladı, qələmin qapağını çıxardı və onu boyanmış hüceyrələrdən birinə qoydu. Sonra Petya qapağı bir boyanmış hüceyrədən digərinə köçürür, bu hüceyrə əvvəlki ilə eyni sırada və ya eyni sütunda yerləşməlidir. Petya müəyyən bir boyanmış hüceyrəni seçdi və qapağı başlanğıc hüceyrədən mümkün qədər az hərəkətlə ora köçürmək istəyir.

Kağızın ölçüləri, boyanmış hüceyrələrin konfiqurasiyası, qapağın yerləşməsi və hədəf hüceyrə haqqında məlumatlara əsasən, Petya qapağı başlanğıc hüceyrədən hədəf hüceyrəyə öz qaydalarına uyğun olaraq köçürə biləcəyi ən az mümkün sayda hərəkətləri tapacaq bir proqram yazın.

Giriş verilənləri

Birinci sətirdə vərəqi təşkil edən hüceyrələrin N sətir və M sütun sayını göstərən iki tam ədəd verilir (2 ≤ M ≤ N ≤ 1000). Növbəti N sətirin hər biri M simvolu ehtiva edir:

1. x (kiçik latın hərfi) - boyanmış hüceyrə.

2. . (nöqtə) - boş hüceyrə.

3. o (kiçik latın hərfi) - başlanğıc hüceyrə.

4. + (plus) - hədəf hüceyrə.

Giriş məlumatlarında dəqiq bir başlanğıc və dəqiq bir hədəf hüceyrə verilir.

Çıxış verilənləri

Bir ədəd çıxarın - Petya'nın məqsədinə çatması üçün qapağı köçürməli olduğu ən az hərəkət sayı. Əgər verilmiş qaydalara görə hədəf hüceyrəyə çatmaq mümkün deyilsə, -1 çıxarın.

Nümunələr