Problem: Problem Statement

You have a rectangular board with square cells arranged in $H$ rows and $W$ columns. The rows are numbered $1$ through $H$ from top to bottom, and the columns are numbered $1$ through $W$ from left to right. The cell at the row $i$ and the column $j$ is denoted by $(i, j)$. Each cell on the board is colored in either Black or White.

You will paint the board as follows:

1. Choose a cell $(i, j)$ and a color $c$, each uniformly at random, where $1 \le i \le H$, $1 \le j \le W$, and $c \in \\{{\rm Black}, {\rm White}\\}$.

2. Paint the cells $(i', j')$ with the color $c$ for any $1 \le i' \le i$ and $1 \le j' \le j$.




Here's an example of the painting operation. You have a $3 \times 4$ board with the coloring depicted in the left side of the figure below. If your random choice is the cell $(2, 3)$ and the color Black, the board will become as shown in the right side of the figure. $6$ cells will be painted with Black as the result of this operation. Note that we count the cells "painted" even if the color is not actually changed by the operation, like the cell $(1, 2)$ in this example.

<image>
Fig: An example of the painting operation


Given the initial coloring of the board and the desired coloring, you are supposed to perform the painting operations repeatedly until the board turns into the desired coloring. Write a program to calculate the expected total number of painted cells in the sequence of operations.

Input

The input consists of several datasets. The number of datasets is at most $100$.

The first line of each dataset contains two integers $H$ and $W$ ($1 \le H, W \le 5$), the numbers of rows and columns of the board respectively. Then given are two coloring configurations of the board, where the former is the initial coloring and the latter is the desired coloring. A coloring configuration is described in $H$ lines, each of which consists of $W$ characters. Each character is either B or W, denoting a Black cell or a White cell, respectively. There is one blank line between two configurations, and also after each dataset. You can assume that the resulting expected value for each dataset will not exceed $10^9$.

The input is terminated by a line with two zeros, and your program should not process this as a dataset.

Output

For each dataset, your program should output the expected value in a line. The absolute error or the relative error in your answer must be less than $10^{-6}$.

Sample Input


1 2
BB

WW

2 1
B
W

B
W

2 2
BW
BW

WW
WW

3 4
BBBB
BBBB
BBBB

WWWW
WWWW
WWWW

5 5
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB

BBBBB
BBBWB
BBBBB
BWBBB
BBBBB

0 0

Output for the Sample Input


6.0000000000
0.0000000000
12.8571428571
120.0000000000
23795493.8449918639





Example

Input

1 2
BB

WW

2 1
B
W

B
W

2 2
BW
BW

WW
WW

3 4
BBBB
BBBB
BBBB

WWWW
WWWW
WWWW

5 5
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB

BBBBB
BBBWB
BBBBB
BWBBB
BBBBB

0 0


Output

6.0000000000
0.0000000000
12.8571428571
120.0000000000
23795493.8449918639

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
//#define EPS 0.000000001
using namespace std;

#define EPS 0.00000000001

#define NUM 6
#define MAX 252

typedef vector<double> V;
typedef vector<V> MATRIX;

struct Info{
	Info(int arg_state,int arg_num_paint){
		state = arg_state;
		num_paint = arg_num_paint;
	}
	int state,num_paint;
};

int H,W;
int POW[26],state_index,ans_state;
int first_state;
map<int,int> STATE,PAINT;
char first[NUM][NUM],last[NUM][NUM],color[2] = {'B','W'};
double P_table[MAX][MAX],ADD_table[MAX][MAX];


int get_code(char table[NUM][NUM]){

	int ret = 0;
	int index = 0;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			if(table[row][col] == 'B'){
				ret += POW[index];
			}
			index++;
		}
	}
	return ret;
}

int get_state(char table[NUM][NUM]){

	int first_code = get_code(table); //最初の状態

	auto at1 = PAINT.find(first_code);
	auto at2 = STATE.find(PAINT[first_code]);

	if(at1 != PAINT.end() && at2 != STATE.end()){

		return STATE[PAINT[first_code]]; //既に状態が登録済ならreturn
	}


	char work[NUM][NUM];

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			work[row][col] = table[row][col];
		}
	}

	//★★正しい状態に遷移させるために、最小限塗らなければならない場所が同一ならば、同じ状態と見なす★★

	int index = H*W-1,paint_state = 0;

	for(int row = H-1; row >= 0; row--){
		for(int col = W-1; col >= 0; col--){
			if(work[row][col] != last[row][col]){ //左上方向に向かって塗らなければならない場所を探す

				paint_state += POW[index];
				for(int a = row; a >= 0; a--){
					for(int b = col; b >= 0; b--){
						work[a][b] = last[row][col];
					}
				}
			}
			index--;
		}
	}

	at2 = STATE.find(paint_state);

	if(at2 != STATE.end()){ //塗った状態は登録されている場合

		PAINT[first_code] = paint_state;
		return STATE[paint_state];
	}

	PAINT[first_code] = paint_state; //first_codeが塗らなければならない場所を登録
	return STATE[paint_state] = state_index++;
}

void calc_states(char first_table[NUM][NUM]){

	int first_code = get_code(first_table); //最初の状態

	queue<int> Q;
	Q.push(first_code);

	int base_code,base_state,tmp_code,tmp_state,index;
	char base_table[NUM][NUM],work[NUM][NUM];

	bool check[MAX];

	for(int i = 0; i < MAX; i++){

		check[i] = false;
	}

	while(!Q.empty()){

		base_code = Q.front();
		Q.pop();

		index = 0;

		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				if(base_code & (1 << index)){
					base_table[row][col] = 'B';
				}else{
					base_table[row][col] = 'W';
				}
				index++;
			}
		}

		base_state = get_state(base_table);
		check[base_state] = true;

		//次に遷移する状態を全探索する

		int count;

		//次の状態を全て試す(最大H*W*2通り)
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				for(int a = 0; a < 2; a++){

					for(int i = 0; i < H; i++){
						for(int k = 0; k < W; k++){
							work[i][k] = base_table[i][k];
						}
					}

					count = 0;

					for(int i = row; i >= 0; i--){
						for(int k = col; k >= 0; k--){
							count++;
							work[i][k] = color[a];
						}
					}


					tmp_state = get_state(work);

					P_table[base_state][tmp_state] += 1.0/(double)(2*H*W);
					ADD_table[base_state][tmp_state] += ((row+1)*(col+1))/(double)(2*H*W);

					if(!check[tmp_state]){

						check[tmp_state] = true;
						tmp_code = get_code(work);

						index = 0;

						for(int a = 0; a < row; a++){
							for(int b = 0; b < col; b++){
								if(tmp_code & (1 << index)){

									work[a][b] = 'B';

								}else{
									work[a][b] = 'W';
								}
							}
						}

						Q.push(tmp_code);
					}
				}
			}
		}
	}
}

MATRIX gauss_jordan(MATRIX A,int SIZE){

	MATRIX C(SIZE,V(SIZE+1));

	for(int row = 0; row < SIZE; row++){
		for(int col = 0; col <= SIZE; col++){
			C[row][col] = A[row][col];
		}
	}

	int base_row;
	double tmp;

	for(int i = 0; i < SIZE; i++){
		base_row = i;
		for(int row = i+1; row < SIZE; row++){
			if(fabs(C[row][i]) > fabs(C[base_row][i])){
				base_row = row;
			}
		}

		if(fabs(C[base_row][i]) < EPS)continue; //操作不要

		if(base_row != i)swap(C[base_row],C[i]);

		tmp = C[i][i]; //係数
		for(int col = 0; col <= SIZE; col++){ //基準行の係数を1にする
			C[i][col] /= tmp;
		}

		for(int row = 0; row < SIZE; row++){
			if(row == i || fabs(C[row][i]) < EPS)continue; //基準行、または該当列が0ならSKIP

			tmp = C[row][i];

			for(int col = i; col <= SIZE; col++){
				C[row][col] -= C[i][col]*tmp;
			}
		}
	}

	return C;
}

void func(){

	for(int row = 0; row < H; row++){
		scanf("%s",first[row]);
	}


	for(int row = 0; row < H; row++){

		scanf("%s",last[row]);
	}

	STATE.clear();
	PAINT.clear();

	state_index = 0;

	for(int i = 0; i < MAX; i++){
		for(int k = 0; k < MAX; k++){
			P_table[i][k] = 0;
			ADD_table[i][k] = 0;
		}
	}

	calc_states(first);

	first_state = get_state(first);
	ans_state = get_state(last);

	//return;
	MATRIX A(state_index,V(state_index+1));

	for(int row = 0; row < state_index; row++){
		for(int col = 0; col <= state_index; col++){
			A[row][col] = 0;
		}
	}

	for(int i = 0; i < state_index; i++){

		A[i][i] = 1.0;

		if(i == ans_state)continue;

		for(int k = 0; k < state_index; k++){

			A[i][k] -= P_table[i][k];
			A[i][state_index] += ADD_table[i][k]; //塗る枚数
		}
	}

	A = gauss_jordan(A,state_index);

	printf("%.10lf\n",A[first_state][state_index]);

	return;
}


int main(){

	POW[0] = 1;

	for(int i = 1; i < 26; i++){

		POW[i] = POW[i-1]*2;
	}

	while(true){

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

		func();
	}

	return 0;
}