Problem: Mary Thomas has a number of sheets of squared paper. Some of squares are painted either in black or some colorful color (such as red and blue) on the front side. Cutting off the unpainted part, she will have eight opened-up unit cubes. A unit cube here refers to a cube of which each face consists of one square.

She is going to build those eight unit cubes with the front side exposed and then a bicube with them. A bicube is a cube of the size 2 × 2 × 2, consisting of eight unit cubes, that satisfies the following conditions:

* faces of the unit cubes that comes to the inside of the bicube are all black;
* each face of the bicube has a uniform colorful color; and
* the faces of the bicube have colors all different.



Your task is to write a program that reads the specification of a sheet of squared paper and decides whether a bicube can be built with the eight unit cubes resulting from it.



Input

The input contains the specification of a sheet. The first line contains two integers H and W, which denote the height and width of the sheet (3 ≤ H, W ≤ 50). Then H lines follow, each consisting of W characters. These lines show the squares on the front side of the sheet. A character represents the color of a grid: alphabets and digits ('A' to 'Z', 'a' to 'z', '0' to '9') for colorful squares, a hash ('#') for a black square, and a dot ('.') for an unpainted square. Each alphabet or digit denotes a unique color: squares have the same color if and only if they are represented by the same character.

Each component of connected squares forms one opened-up cube. Squares are regarded as connected when they have a common edge; those just with a common vertex are not.

Output

Print "Yes" if a bicube can be built with the given sheet; "No" otherwise.

Examples

Input

3 40
.a....a....a....a....f....f....f....f...
#bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#be#.
.#....#....#....#....#....#....#....#...


Output

Yes


Input

3 40
.a....a....a....a....f....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#be#.
.#....#....#....#....#....#....#....#...


Output

Yes


Input

5 35
.a....a....a....a....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.
.#..f.#....#....#....#....#....#...
..e##..............................
.b#................................


Output

Yes


Input

3 40
.a....a....a....a....f....f....f....f...
bc#.#cd#.#de#.#eb#.#cb#.#dc#.#ed#.#eb#.
.#....#....#....#....#....#....#....#...


Output

No

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;


struct LOC{
	LOC(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

//0:上 1:北 2:東 3:西 4:南 5:裏側
struct Dice{

	void roll(char dst){
		for(int i = 0; i < 6; i++) work[i] = words[i];
		switch(dst){
		case 'E':
			setWords(work[3],work[1],work[0],work[5],work[4],work[2]);
			break;
		case 'S':
			setWords(work[1],work[5],work[2],work[3],work[0],work[4]);
			break;
		case 'N':
			setWords(work[4],work[0],work[2],work[3],work[5],work[1]);
			break;
		case 'W':
			setWords(work[2],work[1],work[5],work[0],work[4],work[3]);
			break;
		}
	};


	void paint(char ch){

		words[5] = ch;
	}

	void setWords(char n0,char n1,char n2,char n3,char n4,char n5){
		words[0] = n0;
		words[1] = n1;
		words[2] = n2;
		words[3] = n3;
		words[4] = n4;
		words[5] = n5;
	}

	void init(){
		for(int i = 0; i < 6; i++){
			words[i] = '@';
		}
	}

	int count_blank(){

		int ret = 0;

		for(int i = 0; i < 6; i++){
			if(words[i] == '@')ret++;
		}
		return ret;
	}

	void set(Dice arg){
		for(int i = 0; i < 6; i++){
			words[i] = arg.words[i];
		}
	}

	char words[6],work[6];
};


int H,W;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
char work[55][55],table[55][55];
char order[25] = "NNNNWNNNWNNNENNNENNNWNNN",dir[5] = "NWES";
bool visited[55][55],FLG;
Dice dice[8],DICE,BICUBE[2][2][2];


bool rangeCheck(int row,int col){

	return row >= 0 && row <= H-1 && col >= 0 && col <= W-1;
}

void recursive(int depth,Dice dice,int row,int col){

	if(depth == 8 || FLG == true)return;

	dice.paint(table[row][col]);

	if(dice.count_blank() == 0){
		DICE.set(dice);

		FLG = true;
		return;
	}

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

		int adj_row = row+diff_row[i];
		int adj_col = col+diff_col[i];

		if(rangeCheck(adj_row,adj_col) == false || table[adj_row][adj_col] == '.')continue;

		Dice next_dice;
		next_dice.set(dice);

		next_dice.roll(dir[i]);
		recursive(depth+1,next_dice,adj_row,adj_col);
	}
}

int main(){

	scanf("%d %d",&H,&W);

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

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

	//シートを裏返す
	for(int col = 0; col < W; col++){
		for(int row = 0; row < H; row++){

			table[row][col] = work[row][W-1-col];
		}
	}

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

	//サイコロの表面に色を塗る
	int index = 0;

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

			if(table[row][col] != '.' && visited[row][col] == false){

				Dice tmp_dice;
				tmp_dice.init();

				FLG = false;
				recursive(0,tmp_dice,row,col);

				dice[index++].set(DICE);

				queue<LOC> Q;
				visited[row][col] = true;

				Q.push(LOC(row,col));

				while(!Q.empty()){

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

						int adj_row = Q.front().row+diff_row[i];
						int adj_col = Q.front().col+diff_col[i];

						if(rangeCheck(adj_row,adj_col) == false || table[adj_row][adj_col] == '.' ||
								visited[adj_row][adj_col] == true)continue;

						visited[adj_row][adj_col] = true;
						Q.push(LOC(adj_row,adj_col));
					}
					Q.pop();
				}
			}
		}
	}

	int black_pos[6][3] = {{0,1,3},{0,2,4},{0,3,4},{1,2,5},{1,3,5},{2,4,5}};
	int color_pos[6][3] = {{2,4,5},{1,3,5},{1,2,5},{0,3,4},{0,2,4},{0,1,3}};

	int X[6] = {1,0,1,0,1,0};
	int Y[6] = {0,1,1,0,0,1};
	int Z[6] = {0,0,0,1,1,1};

	//dice[0]を(0,0,0)にセットする
	for(int loop = 0; loop < 24; loop++){

		dice[0].roll(order[loop]);
		if(dice[0].words[0] == '#' && dice[0].words[1] == '#' && dice[0].words[2] == '#'){

			BICUBE[0][0][0].set(dice[0]);

			char color[6];

			color[3] = BICUBE[0][0][0].words[3];
			color[4] = BICUBE[0][0][0].words[4];
			color[5] = BICUBE[0][0][0].words[5];

			for(int i = 1; i <= 7; i++){ //(1,1,1)のダイスを設定

				bool check[8];
				check[0] = true;

				for(int k = 1; k < 8; k++){
					check[k] = false;
				}

				check[i] = true;
				BICUBE[1][1][1].set(dice[i]);

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

					BICUBE[1][1][1].roll(order[k]);

					if(BICUBE[1][1][1].words[3] == '#' && BICUBE[1][1][1].words[4] == '#' && BICUBE[1][1][1].words[5] == '#'){

						color[0] = BICUBE[1][1][1].words[0];
						color[1] = BICUBE[1][1][1].words[1];
						color[2] = BICUBE[1][1][1].words[2];

						bool color_FLG =true;
						for(int a = 0; a < 5; a++){
							for(int b = a+1; b < 6; b++){
								if(color[a] == color[b]){

									color_FLG = false;
									break;
								}
							}
							if(!color_FLG)break; //面の色は全て異なっていないと不可
						}

						if(!color_FLG)continue;

						for(int loc = 0; loc < 6; loc++){
							if(color[loc] == '#'){
								color_FLG = false;
								break;
							}
						}

						if(!color_FLG)continue;


						int index = 0;
						int sequence[6];

						for(int g = 1; g <= 7; g++){
							if(check[g])continue;

							sequence[index++] = g;
						}

						do{

							for(int loc = 0; loc < 6; loc++){ //残り6箇所

								int x = X[loc];
								int y = Y[loc];
								int z = Z[loc];

								BICUBE[x][y][z].set(dice[sequence[loc]]);

								bool tmp_FLG = false;

								for(int b = 0; b < 24; b++){ //位置のループ

									BICUBE[x][y][z].roll(order[b]);

									tmp_FLG = true;

									for(int c = 0; c < 3; c++){ //黒の位置
										if(BICUBE[x][y][z].words[black_pos[loc][c]] != '#'){
											tmp_FLG = false;
											break;
										}
									}

									if(!tmp_FLG)continue;

									for(int c = 0; c < 3; c++){
										if(BICUBE[x][y][z].words[color_pos[loc][c]] != color[color_pos[loc][c]]){

											tmp_FLG = false;
											break;
										}
									}

									if(!tmp_FLG)continue;

									break;
								}

								if(!tmp_FLG)break;

								if(loc == 5){
									printf("Yes\n");
									return 0;
								}
							}

						}while(next_permutation(sequence,sequence+6));
					}
				}
			}
		}
	}

	printf("No\n");

	return 0;
}