Problem: In sliding block puzzles, we repeatedly slide pieces (blocks) to open spaces within a frame to establish a goal placement of pieces.

A puzzle creator has designed a new puzzle by combining the ideas of sliding block puzzles and mazes. The puzzle is played in a rectangular frame segmented into unit squares. Some squares are pre-occupied by obstacles. There are a number of pieces placed in the frame, one 2 × 2 king piece and some number of 1 × 1 pawn pieces. Exactly two 1 × 1 squares are left open. If a pawn piece is adjacent to an open square, we can slide the piece there. If a whole edge of the king piece is adjacent to two open squares, we can slide the king piece. We cannot move the obstacles. Starting from a given initial placement, the objective of the puzzle is to move the king piece to the upper-left corner of the frame.

The following figure illustrates the initial placement of the fourth dataset of the sample input.

<image>


Figure E.1: The fourth dataset of the sample input.

Your task is to write a program that computes the minimum number of moves to solve the puzzle from a given placement of pieces. Here, one move means sliding either king or pawn piece to an adjacent position.



Input

The input is a sequence of datasets. The first line of a dataset consists of two integers H and W separated by a space, where H and W are the height and the width of the frame. The following H lines, each consisting of W characters, denote the initial placement of pieces. In those H lines, 'X', 'o', '*', and '.' denote a part of the king piece, a pawn piece, an obstacle, and an open square, respectively. There are no other characters in those H lines. You may assume that 3 ≤ H ≤ 50 and 3 ≤ W ≤ 50.

A line containing two zeros separated by a space indicates the end of the input.

Output

For each dataset, output a line containing the minimum number of moves required to move the king piece to the upper-left corner. If there is no way to do so, output -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

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
#define  MP make_pair
#define  PB push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define fi first
#define se second
#define inf 1000000007
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

pair<pair<int,int>,pair<int,int> >tugi(int i,int j,int dir){
    if(dir==0){
        return MP(MP(i,j+2),MP(i+1,j+2));
    }else if(dir==1){
        return MP(MP(i,j-1),MP(i+1,j-1));
    }else if(dir==2){
        return MP(MP(i+2,j),MP(i+2,j+1));
    }else if(dir==3){
        return MP(MP(i-1,j),MP(i-1,j+1));
    }
}
pair<pair<int,int>,pair<int,int> > mae(int i,int j,int dir){
    if(dir==0){
        return MP(MP(i,j-1),MP(i+1,j-1));
    }else if(dir==1){
        return MP(MP(i,j+2),MP(i+1,j+2));
    }else if(dir==2){
        return MP(MP(i-1,j),MP(i-1,j+1));
    }else if(dir==3){
        return MP(MP(i+2,j),MP(i+2,j+1));
    }
}

int n,m;
vector<string>s;
vector<vector<bool> > ng;
vector<vector<vector<bool> > > flag;

bool lmov(int i,int j,int dir){
    if(j+dx[dir]<0||j+dx[dir]+1>=m)return false;
    if(i+dy[dir]<0||i+dy[dir]+1>=n)return false;
    if(s[i+dy[dir]][j+dx[dir]]=='*')return false;
    if(s[i+dy[dir]+1][j+dx[dir]]=='*')return false;
    if(s[i+dy[dir]][j+dx[dir]+1]=='*')return false;
    if(s[i+dy[dir]+1][j+dx[dir]+1]=='*')return false;
    return true;
}
bool smov(int i,int j,int dir){
    if(j+dx[dir]<0||j+dx[dir]>=m)return false;
    if(i+dy[dir]<0||i+dy[dir]>=n)return false;
    if(s[i+dy[dir]][j+dx[dir]]=='*')return false;
    return true;
}

int oridst(pair<int,int>b,pair<int,int>a){
    //cerr << a.fi << " " << a.se << " "<< b.fi << " " << b.se << endl;
    queue<pair<int,pair<int,int> > >q;
    q.push(MP(0,a));
    vector<vector<bool> > reached(n,vector<bool>(m));
    int res = inf;
    while(!q.empty()){
        auto x= q.front();
        if(x.se==b){
            res = x.fi;
            break;
        }
        q.pop();
        rep(i,4){
            if(smov(x.se.fi,x.se.se,i)){
                if(s[x.se.fi+dy[i]][x.se.se+dx[i]]!='X'){
                    if(!reached[x.se.fi+dy[i]][x.se.se+dx[i]]){
                        reached[x.se.fi+dy[i]][x.se.se+dx[i]] = true;
                        q.push(MP(x.fi+1,MP(x.se.fi+dy[i],x.se.se+dx[i])));
                    }
                }
            }
        }
    }


    return res+1;
}
int secdst(pair<int,int>b,pair<int,int>a,pair<int,int>now){
    //cerr << a.fi << " " << a.se << " "<< b.fi << " " << b.se << endl;
    queue<pair<int,pair<int,int> > >q;
    set<pair<int,int> > st;
    st.insert(MP(now.fi,now.se));
    st.insert(MP(now.fi+1,now.se));
    st.insert(MP(now.fi+1,now.se+1));
    st.insert(MP(now.fi,now.se+1));
    q.push(MP(0,a));
    vector<vector<bool> > reached(n,vector<bool>(m));
    int res = inf;
    while(!q.empty()){
        auto x= q.front();
        if(x.se==b){
            res = x.fi;
            break;
        }
        q.pop();
        rep(i,4){
            if(smov(x.se.fi,x.se.se,i)){
                if(st.count(MP(x.se.fi+dy[i],x.se.se+dx[i]))==0){
                    if(!reached[x.se.fi+dy[i]][x.se.se+dx[i]]){
                        reached[x.se.fi+dy[i]][x.se.se+dx[i]] = true;
                        q.push(MP(x.fi+1,MP(x.se.fi+dy[i],x.se.se+dx[i])));
                    }
                }
            }
        }
    }


    return res+1;
}
int main(){
    
    while(1){
        cin >> n >> m;
        if(n==0&&m==0)break;
        s.resize(n);
        rep(i,n)cin >> s[i];
        ng.resize(n);
        rep(i,n)ng[i].resize(m);
        int px = 10000;
        int py = 10000;
        vector<pair<int,int> > oridot; 
        rep(i,n){
            rep(j,m){
                if(s[i][j]=='*'){
                    ng[i][j] = 1;
                }
                if(s[i][j]=='X'){
                    py = min(py,i);
                    px = min(px,j);
                }
                if(s[i][j]=='.'){
                    oridot.push_back(MP(i,j));
                }
            }
        }
        if(py==0&&px==0){
            cout << 0 << endl;
            continue;
        }
        vector<vector<vector<vector<bool> > > >reached(n,vector<vector<vector<bool>>>(m,vector<vector<bool>>(4,vector<bool>(4))));
        
        priority_queue<pair<pair<int,pair<int,int> >,pair<int,int> >,vector<pair<pair<int,pair<int,int>>,pair<int,int> > >,greater<pair<pair<int,pair<int,int>>,pair<int,int> > > > pq;
        for(int i=0;i<4;i++){
            if(lmov(py,px,i)){
                pair<int,int> t1,t2;
                t1 = tugi(py,px,i).fi;
                t2 = tugi(py,px,i).se;
                if(s[t1.fi][t1.se]=='.'&&s[t2.fi][t2.se]=='.'){
                    pq.push(MP(MP(1,MP(i,0)),MP(py+dy[i],px+dx[i])));
                    reached[py+dy[i]][px+dx[i]][i][0]= true;
                    reached[py+dy[i]][px+dx[i]][i][1]= true;
                    reached[py+dy[i]][px+dx[i]][i][2]= true;
                    reached[py+dy[i]][px+dx[i]][i][3]= true;
                }else if(s[t1.fi][t1.se]=='o'&&s[t2.fi][t2.se]=='.'){
                    int dst;
                    if(t2==oridot[0]){
                        dst = oridst(t1,oridot[1]);
                    }else{
                        dst = oridst(t1,oridot[0]);
                    }
                    if(dst>=inf)continue;
                    pq.push(MP(MP(dst,MP(i,0)),MP(py+dy[i],px+dx[i])));
                    reached[py+dy[i]][px+dx[i]][i][0]= true;
                    reached[py+dy[i]][px+dx[i]][i][1]= true;
                    reached[py+dy[i]][px+dx[i]][i][2]= true;
                    reached[py+dy[i]][px+dx[i]][i][3]= true;
                }else if(s[t1.fi][t1.se]=='.'&&s[t2.fi][t2.se]=='o'){
                    int dst;
                    if(t1==oridot[0]){
                        dst = oridst(t2,oridot[1]);
                    }else{
                        dst = oridst(t2,oridot[0]);
                    }
                    if(dst>=inf)continue;
                    pq.push(MP(MP(dst,MP(i,0)),MP(py+dy[i],px+dx[i])));
                    reached[py+dy[i]][px+dx[i]][i][0]= true;
                    reached[py+dy[i]][px+dx[i]][i][1]= true;
                    reached[py+dy[i]][px+dx[i]][i][2]= true;
                    reached[py+dy[i]][px+dx[i]][i][3]= true;
                }else{
                    int dst= oridst(t2,oridot[1])+oridst(t1,oridot[0]);
                    dst = min(dst,oridst(t2,oridot[0])+oridst(t1,oridot[1]));
                    if(dst>=inf)continue;
                    pq.push(MP(MP(dst-1,MP(i,0)),MP(py+dy[i],px+dx[i])));
                    reached[py+dy[i]][px+dx[i]][i][0]= true;
                    reached[py+dy[i]][px+dx[i]][i][1]= true;
                    reached[py+dy[i]][px+dx[i]][i][2]= true;
                    reached[py+dy[i]][px+dx[i]][i][3]= true;
                }
            }
        }
        // while(!pq.empty()){
        //     auto x = pq.top();
        //     cerr << x.first.first << " " << x.fi.se << endl;
        //     pq.pop();
        // }
        reached[py][px][0][0]= true;
        reached[py][px][1][0]= true;
        reached[py][px][2][0]= true;
        reached[py][px][3][0]= true;
        reached[py][px][0][1]= true;
        reached[py][px][1][1]= true;
        reached[py][px][2][1]= true;
        reached[py][px][3][1]= true;
        reached[py][px][0][2]= true;
        reached[py][px][1][2]= true;
        reached[py][px][2][2]= true;
        reached[py][px][3][2]= true;
        reached[py][px][0][3]= true;
        reached[py][px][1][3]= true;
        reached[py][px][2][3]= true;
        reached[py][px][3][3]= true;
        int ans = inf;
        vector<vector<vector<int> > >shortest(n,vector<vector<int>>(m,vector<int>(4,inf)));
        
        while(!pq.empty()){
            auto x = pq.top();
            pq.pop();

            if(x.se==MP(0,0)){
                ans = min(ans,x.fi.fi);
                break;
            }
            auto now = x.second;
            //cerr << now.fi << " " << now.se << " " << x.fi.se << "  " << x.fi.fi  << endl;
            int dir = x.fi.se.fi;
            int dir2 = x.fi.se.se;
            int dst = x.fi.fi;
            shortest[now.fi][now.se][dir]= min(shortest[now.fi][now.se][dir],dst);
            if(shortest[now.fi][now.se][dir]!=dst)continue;
            // if(reached[now.fi][now.se][dir])continue;
            for(int i=0;i<4;i++){
                if(lmov(now.fi,now.se,i)&&!reached[now.fi+dy[i]][now.se+dx[i]][i][dir]){
                    pair<int,int> t1,t2,s1,s2;
                    t1 = tugi(now.fi,now.se,i).fi;
                    t2 = tugi(now.fi,now.se,i).se;
                    s1 = mae(now.fi,now.se,dir).fi;
                    s2 = mae(now.fi,now.se,dir).se;
                    // cerr << t1.first << " " << t1.second << " " << t2.first << " " << t2.second<< endl;
                    // cerr << s1.first << " " << s1.second << " " << s2.first << " " << s2.second<< endl;
                    int dst2= secdst(t2,s1,now)+secdst(t1,s2,now);
                    
                    dst2 = min(dst2,secdst(t2,s2,now)+secdst(t1,s1,now));
                    //cerr << dst2 << endl;
                    if(dst-1+dst2>=inf)continue;
                    if(shortest[now.fi+dy[i]][now.se+dx[i]][dir]<=dst-1+dst2)continue;
                    shortest[now.fi][now.se][dir]=dst-1+dst2;
                    reached[now.fi+dy[i]][now.se+dx[i]][i][dir]= true;
                    pq.push(MP(MP(dst-1+dst2,MP(i,dir)),MP(now.fi+dy[i],now.se+dx[i])));
                    
                }
            }
        }
        if(ans==inf){
            cout << -1 << endl;
        }else{
            cout << ans << endl;
        }
        s.clear();
        ng.clear();
        flag.clear();
    }
    return 0;
}