Problem: Mr. Schwarz was a famous powerful pro wrestler. He starts a part time job as a warehouseman. His task is to move a cargo to a goal by repeatedly pushing the cargo in the warehouse, of course, without breaking the walls and the pillars of the warehouse.

There may be some pillars in the warehouse. Except for the locations of the pillars, the floor of the warehouse is paved with square tiles whose size fits with the cargo. Each pillar occupies the same area as a tile.

<image>

Initially, the cargo is on the center of a tile. With one push, he can move the cargo onto the center of an adjacent tile if he is in proper position. The tile onto which he will move the cargo must be one of (at most) four tiles (i.e., east, west, north or south) adjacent to the tile where the cargo is present.

To push, he must also be on the tile adjacent to the present tile. He can only push the cargo in the same direction as he faces to it and he cannot pull it. So, when the cargo is on the tile next to a wall (or a pillar), he can only move it along the wall (or the pillar). Furthermore, once he places it on a corner tile, he cannot move it anymore.

He can change his position, if there is a path to the position without obstacles (such as the cargo and pillars) in the way. The goal is not an obstacle. In addition, he can move only in the four directions (i.e., east, west, north or south) and change his direction only at the center of a tile.

As he is not so young, he wants to save his energy by keeping the number of required pushes as small as possible. But he does not mind the count of his pedometer, because walking is very light exercise for him.

Your job is to write a program that outputs the minimum number of pushes required to move the cargo to the goal, if ever possible.



Input

The input consists of multiple maps, each representing the size and the arrangement of the warehouse. A map is given in the following format.


w h
d11 d12 d13 ... d1w
d21 d22 d23 ... d2w
...
dh1 dh2 dh3 ... dhw


The integers w and h are the lengths of the two sides of the floor of the warehouse in terms of widths of floor tiles. w and h are less than or equal to 7. The integer dij represents what is initially on the corresponding floor area in the following way.

0: nothing (simply a floor tile)

1: a pillar

2: the cargo

3: the goal

4: the warehouseman (Mr. Schwarz)

Each of the integers 2, 3 and 4 appears exactly once as dij in the map. Integer numbers in an input line are separated by at least one space character. The end of the input is indicated by a line containing two zeros.

Output

For each map, your program should output a line containing the minimum number of pushes. If the cargo cannot be moved to the goal, -1 should be output instead.

Example

Input

5 5
0 0 0 0 0
4 2 0 1 1
0 1 0 0 0
1 0 0 0 3
1 0 0 0 0
5 3
4 0 0 0 0
2 0 0 0 0
0 0 0 0 3
7 5
1 1 4 1 0 0 0
1 1 2 1 0 0 0
3 0 0 0 0 0 0
0 1 0 1 0 0 0
0 0 0 1 0 0 0
6 6
0 0 0 0 0 3
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 2 0 0 0 0
4 0 0 0 0 0
0 0


Output

5
-1
11
8

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int W,H;
int map[7][7];
int div_row[4] = {-1,0,0,1},div_col[4] = {0,-1,1,0};

struct Info{
	void set(int arg_cargo_row,int arg_cargo_col,int arg_man_row,int arg_man_col,int arg_push_num){
		cargo_row = arg_cargo_row;
		cargo_col = arg_cargo_col;
		man_row = arg_man_row;
		man_col = arg_man_col;
		push_num = arg_push_num;
	}

	int cargo_row,cargo_col,man_row,man_col,push_num;
};

enum LOC{
	UE,
	SHITA,
	MIGI,
	HIDARI,
};

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

void recursive(int distance[7][7],int row,int col,int to_row,int to_col){
	for(int i = 0; i < 4; i++){
		int next_row = row+div_row[i],next_col = col+div_col[i];
		if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != 1 && distance[next_row][next_col] > distance[row][col]+1){
			distance[next_row][next_col] = distance[row][col]+1;
			if(next_row == to_row && next_col == to_col)return;
			recursive(distance,next_row,next_col,to_row,to_col);
		}
	}
}

bool isMoveable(int cargo_row,int cargo_col,LOC current_loc,LOC to_loc){ //curent_loc:???????????¨??° to_loc:???????????????

	int distance[7][7];
	for(int i = 0; i < 7; i++){
		for(int k = 0; k < 7; k++){
			distance[i][k] = BIG_NUM;
		}
	}

	switch(current_loc){
	case UE:
		switch(to_loc){
		case MIGI:
			if(rangeCheck(cargo_row,cargo_col+1) == false || map[cargo_row][cargo_col+1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row-1][cargo_col] = 0;

			recursive(distance,cargo_row-1,cargo_col,cargo_row,cargo_col+1);

			if(distance[cargo_row][cargo_col+1] != BIG_NUM)return true;

			break;
		case HIDARI:
			if(rangeCheck(cargo_row,cargo_col-1) == false || map[cargo_row][cargo_col-1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row-1][cargo_col] = 0;

			recursive(distance,cargo_row-1,cargo_col,cargo_row,cargo_col-1);

			if(distance[cargo_row][cargo_col-1] != BIG_NUM)return true;

			break;
		case SHITA:
			if(rangeCheck(cargo_row+1,cargo_col) == false || map[cargo_row+1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row-1][cargo_col] = 0;

			recursive(distance,cargo_row-1,cargo_col,cargo_row+1,cargo_col);

			if(distance[cargo_row+1][cargo_col] != BIG_NUM)return true;

			break;
		}
		break;
	case SHITA:
		switch(to_loc){
		case MIGI:
			if(rangeCheck(cargo_row,cargo_col+1) == false || map[cargo_row][cargo_col+1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row+1][cargo_col] = 0;

			recursive(distance,cargo_row+1,cargo_col,cargo_row,cargo_col+1);

			if(distance[cargo_row][cargo_col+1] != BIG_NUM)return true;
			break;
		case HIDARI:
			if(rangeCheck(cargo_row,cargo_col-1) == false || map[cargo_row][cargo_col-1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row+1][cargo_col] = 0;

			recursive(distance,cargo_row+1,cargo_col,cargo_row,cargo_col-1);

			if(distance[cargo_row][cargo_col-1] != BIG_NUM)return true;
			break;
		case UE:
			if(rangeCheck(cargo_row-1,cargo_col) == false || map[cargo_row-1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row+1][cargo_col] = 0;

			recursive(distance,cargo_row+1,cargo_col,cargo_row-1,cargo_col);

			if(distance[cargo_row-1][cargo_col] != BIG_NUM)return true;
			break;
		}
		break;
	case MIGI:
		switch(to_loc){
		case UE:
			if(rangeCheck(cargo_row-1,cargo_col) == false || map[cargo_row-1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col+1] = 0;

			recursive(distance,cargo_row,cargo_col+1,cargo_row-1,cargo_col);

			if(distance[cargo_row-1][cargo_col] != BIG_NUM)return true;
			break;
		case SHITA:
			if(rangeCheck(cargo_row+1,cargo_col) == false || map[cargo_row+1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col+1] = 0;

			recursive(distance,cargo_row,cargo_col+1,cargo_row+1,cargo_col);

			if(distance[cargo_row+1][cargo_col] != BIG_NUM)return true;
			break;
		case HIDARI:
			if(rangeCheck(cargo_row,cargo_col-1) == false || map[cargo_row][cargo_col-1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col+1] = 0;

			recursive(distance,cargo_row,cargo_col+1,cargo_row,cargo_col-1);

			if(distance[cargo_row][cargo_col-1] != BIG_NUM)return true;
			break;
		}
		break;
	case HIDARI:
		switch(to_loc){
		case UE:
			if(rangeCheck(cargo_row-1,cargo_col) == false || map[cargo_row-1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col-1] = 0;

			recursive(distance,cargo_row,cargo_col-1,cargo_row-1,cargo_col);

			if(distance[cargo_row-1][cargo_col] != BIG_NUM)return true;
			break;
		case SHITA:
			if(rangeCheck(cargo_row+1,cargo_col) == false || map[cargo_row+1][cargo_col] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col-1] = 0;

			recursive(distance,cargo_row,cargo_col-1,cargo_row+1,cargo_col);

			if(distance[cargo_row+1][cargo_col] != BIG_NUM)return true;
			break;
		case MIGI:
			if(rangeCheck(cargo_row,cargo_col+1) == false || map[cargo_row][cargo_col+1] == 1)return false;

			distance[cargo_row][cargo_col] = -1;
			distance[cargo_row][cargo_col-1] = 0;

			recursive(distance,cargo_row,cargo_col-1,cargo_row,cargo_col+1);

			if(distance[cargo_row][cargo_col+1] != BIG_NUM)return true;
			break;
		}
		break;
	}
	return false;
}

void func(){

	int c_start_row,c_start_col,m_start_row,m_start_col;

	for(int i = 0; i < H; i++){
		for(int k = 0; k < W; k++){
			scanf("%d",&map[i][k]);
			if(map[i][k] == 2){
				c_start_row = i;
				c_start_col = k;
			}else if(map[i][k] == 4){
				m_start_row = i;
				m_start_col = k;
			}
		}
	}

	bool relativePos[H][W][H][W];

	for(int i = 0; i < H; i++){
		for(int k = 0; k < W; k++){
			for(int a = 0; a < H; a++){
				for(int b = 0; b < W; b++)relativePos[i][k][a][b] = false;
			}
		}
	}

	int first_row,first_col;
	int distance[7][7];

	queue<Info> Q;

	for(int i = 0; i < 4; i++){
		first_row = c_start_row+div_row[i];
		first_col = c_start_col+div_col[i];
		if(rangeCheck(first_row,first_col) == true && map[first_row][first_col] != 1){
			for(int a = 0; a < H; a++){
				for(int b = 0; b < W; b++){
					distance[a][b] = BIG_NUM;
				}
			}
			distance[m_start_row][m_start_col] = 0;
			distance[c_start_row][c_start_col] = -1;
			recursive(distance,m_start_row,m_start_col,first_row,first_col);
			if(distance[first_row][first_col] != BIG_NUM){
				Info first;
				first.set(c_start_row,c_start_col,first_row,first_col,0);
				relativePos[c_start_row][c_start_col][first_row][first_col] = true;
				Q.push(first);
			}
		}
	}

	Info current;
	int ans = -1,next_row,next_col;
	LOC nowLoc;

	while(!Q.empty()){
		current = Q.front();
		Q.pop();

		if(map[current.cargo_row][current.cargo_col] == 3){
			ans = current.push_num;
			break;
		}

		if(current.cargo_row == current.man_row){
			if(current.cargo_col > current.man_col){
				nowLoc = HIDARI;
			}else{
				nowLoc = MIGI;
			}
		}else{
			if(current.cargo_row > current.man_row){
				nowLoc = UE;
			}else{
				nowLoc = SHITA;
			}
		}

		for(int i = 0; i < 4; i++){
			next_row = current.cargo_row+div_row[i];
			next_col = current.cargo_col+div_col[i];
			if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != 1 && relativePos[next_row][next_col][current.cargo_row][current.cargo_col] == false){

				Info new_info;

				switch(nowLoc){
				case UE:
					switch(i){
					case 0:
						if(isMoveable(current.cargo_row,current.cargo_col,UE,SHITA)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 1:
						if(isMoveable(current.cargo_row,current.cargo_col,UE,MIGI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 2:
						if(isMoveable(current.cargo_row,current.cargo_col,UE,HIDARI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 3:
						new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
						relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
						Q.push(new_info);
						break;
					}
					break;
				case SHITA:
					switch(i){
					case 0:

						new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
						relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
						Q.push(new_info);
						break;
					case 1:
						if(isMoveable(current.cargo_row,current.cargo_col,SHITA,MIGI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 2:
						if(isMoveable(current.cargo_row,current.cargo_col,SHITA,HIDARI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 3:
						if(isMoveable(current.cargo_row,current.cargo_col,SHITA,UE)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					}
					break;
				case MIGI:
					switch(i){
					case 0:
						if(isMoveable(current.cargo_row,current.cargo_col,MIGI,SHITA)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 1:
						new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
						Q.push(new_info);
						break;
					case 2:
						if(isMoveable(current.cargo_row,current.cargo_col,MIGI,HIDARI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 3:
						if(isMoveable(current.cargo_row,current.cargo_col,MIGI,UE)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					}
					break;
				case HIDARI:
					switch(i){
					case 0:
						if(isMoveable(current.cargo_row,current.cargo_col,HIDARI,SHITA)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 1:
						if(isMoveable(current.cargo_row,current.cargo_col,HIDARI,MIGI)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					case 2:
						new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
						relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
						Q.push(new_info);
						break;
					case 3:
						if(isMoveable(current.cargo_row,current.cargo_col,HIDARI,UE)){

							new_info.set(next_row,next_col,current.cargo_row,current.cargo_col,current.push_num+1);
							relativePos[next_row][next_col][current.cargo_row][current.cargo_col] = true;
							Q.push(new_info);
						}
						break;
					}
					break;
				}
			}
		}

	}

	printf("%d\n",ans);

}

int main(){

	while(true){
		scanf("%d %d",&W,&H);
		if(W == 0 && H == 0)break;

		func();
	}

	return 0;
}