Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT133H - Trò chơi xếp hình

Hãy tưởng tượng lại trò chơi xếp hình với các miếng ghép trượt mà các bạn hay chơi hồi nhỏ!

Một miếng gỗ hình chữ nhật nền có chiều dài H và chiều rộng W, và trong nó chứa các miếng ghép có thể di chuyển xen kẽ với nhau.
Có 3 loại miếng ghép, 1 miếng 2x2 là vua, một số miếng là các con tốt, một số miếng là các vật cản cố định, và có đúng 2 ô trống.
1 miếng ghép chỉ có thể di chuyển theo 1 hướng nếu như ô phía trước (theo hướng ấy) là một ô trống, khi đó, ta sẽ đẩy miếng ghép đi, và tạo ra một ô trống tại vị trí cũ.

Nhiệm vụ của bạn là di chuyển miếng ghép của vua lên góc trên bên trái. Hãy tính số bước thực hiện ít nhất.


Hình vẽ minh họa cho test 4.

Input

Gồm nhiều bộ test.

Mỗi bộ test bắt đầu bằng 2 số H và W (chiều cao và chiều rộng của miếng hình nền, 3 ≤ H, W ≤ 50).

H dòng tiếp theo, mỗi dòng chứa W kí tự, đại diện cho các miếng ghép.
'X', 'o', '*', '.' lần lượt là các ô chứa vua, tốt, ô vật cản và ô trống.

Input kết thúc bởi 2 số 0.

Output

Với mỗi test, in ra số bước di chuyển tối thiểu để di chuyển vua tới góc trên bên trái. Nếu không thực hiện được, in ra -1.

Example

Input:
3 3
oo.
oXX
.XX
3 3
XXo
XX.
o.o
3 5
.o*XX
oooXX
oooo.
7 12
oooooooooooo
ooooo*****oo
oooooo****oo
o**ooo***ooo
o***ooooo..o
o**ooooooXXo
ooooo****XXo
5 30
oooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooo
o***************************oo
XX.ooooooooooooooooooooooooooo
XX.ooooooooooooooooooooooooooo
0 0
Output:
11
0
-1
382
6807

Được gửi lên bởi:adm
Ngày:2013-02-16
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.