Problem: Problem E: Laser Puzzle

An explorer John is now at a crisis! He is entrapped in a W times H rectangular room with a embrasure of laser beam. The embrasure is shooting a deadly dangerous laser beam so that he cannot cross or touch the laser beam. On the wall of this room, there are statues and a locked door. The door lock is opening if the beams are hitting every statue.

In this room, there are pillars, mirrors and crystals. A mirror reflects a laser beam. The angle of a mirror should be vertical, horizontal or diagonal. A crystal split a laser beam into two laser beams with θ±(π/4) where θ is the angle of the incident laser beam. He can push one mirror or crystal at a time. He can push mirrors/crystals multiple times. But he can push up to two of mirrors/crystals because the door will be locked forever when he pushes the third mirrors/crystals.

To simplify the situation, the room consists of W times H unit square as shown in figure 1.

<image>
Figure 1

He can move from a square to the neighboring square vertically or horizontally. Please note that he cannot move diagonal direction. Pillars, mirrors and crystals exist on the center of a square. As shown in the figure 2, you can assume that a mirror/crystal moves to the center of the next square at the next moment when he push it. That means, you don't need to consider a state about pushing a mirror/crystal.

<image>
Figure 2

You can assume the following conditions:

* the direction of laser beams are horizontal, vertical or diagonal,
* the embrasure is shooting a laser beam to the center of the neighboring square,
* the embrasure is on the wall,
* he cannot enter to a square with pillar,
* a mirror reflects a laser beam at the center of the square,
* a mirror reflects a laser beam on the both side,
* a mirror blocks a laser beam if the mirror is parallel to the laser beam,
* a crystal split a laser beam at the center of the square,
* diagonal laser does not hit a statue,
* and he cannot leave the room if the door is hit by a vertical, horizontal or diagonal laser.



In order to leave this deadly room, he should push and move mirrors and crystals to the right position and leave the room from the door. Your job is to write a program to check whether it is possible to leave the room.

Figure 3 is an initial situation of the first sample input.

<image>
Figure 3

Figure 4 is one of the solution for the first sample input.

<image>
Figure 4



Input

The first line of the input contains two positive integers W and H (2 < W, H <= 8). The map of the room is given in the following H lines. The map consists of the following characters:

* '#': wall of the room,
* '*': a pillar,
* 'S': a statue on the wall,
* '/': a diagonal mirror with angle π/4 from the bottom side of the room,
* '\': a diagonal mirror with angle 3π/4 from the bottom side of the room,
* '-': a horizontal mirror,
* '|': a vertical mirror,
* 'O': a crystal,
* '@': the initial position of John,
* '.': an empty floor,
* 'L': the embrasure,
* 'D': the door



The judges also guarantee that this problem can be solved without extraordinary optimizations.

Output

Output "Yes" if it is possible for him to leave the room. Otherwise, output "No".

Examples

Input

7 8
##S####
#.....#
S.O...#
#.*|..#
L..*..#
#.O*..D
#.@...#
#######


Output

Yes


Input

7 8
S####
.....#
S.O...#
.*|..#
L..*..#
.O*..D
.@...#


Output

Yes


Input

8 3
L####
S.../@.#
D#


Output

Yes


Input

8 3
L#####
S...@.#
D#


Output

No

Solution (in CPP):

Solution:
#include <iostream>
#include <queue>
#include <set>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
typedef ull Flg;
typedef pair<int, int> Pos;
typedef pair<Flg, vector<Pos> > Pat;

#define REP(i,n) for(int i=0; i<n; i++)
#define mp make_pair

int W,H;
char FF[10][10];


class Field
{
public:
	char f[10][10];
	Field(char fd[10][10])
	{
		memcpy(f,fd,sizeof(f));
	}
};

class LState
{
public:
	int x,y,d;
	LState(int x, int y, int d)
	:x(x),y(y),d(d)
	{}
};

set<Pat> hg;

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

int rdx[]={-1,-1,-1,0,1,1,1,0};
int rdy[]={1,0,-1,-1,-1,0,1,1};

int Rcnt,Scnt,sx,sy,gx,gy;
char Rtype[1000],Sx[100],Sy[100];


pair<int, int> refcy(int d)
{
	int l=(d+8-1)%8;
	int r=(d+1)%8;

	return mp(l,r);
}

int ref14(int d)
{
	if(d==2) return 6;
	if(d==6) return 2;
	if(d%2==0) return -1;

	if(d==5||d==3) return (d==3?5:3);

	return (d==7?1:7);

}

int ref34(int d)
{
	if(d==4) return 0;
	if(d==0) return 4;
	if(d%2==0) return -1;

	if(d==3||d==1) return (d==3?1:3);

	return (d==5?7:5);
}

int refhor(int d)
{
	if(d==3) return 7;
	if(d==7) return 3;
	if(d%2==1) return -1;

	if(d==2||d==0) return (d==2?0:2);

	return (d==6?4:6);

}

int refver(int d)
{
	if(d==5) return 1;
	if(d==1) return 5;
	if(d%2==1) return -1;

	if(d==2||d==4) return (d==2?4:2);

	return (d==0?6:0);
}

int LaserDir(Field& f, int x, int y)
{
	REP(i,4)
	{
		int tx=x+dx[i], ty=y+dy[i];
		if(tx<0||ty<0||tx>=W||ty>=H) continue;
		if(FF[tx][ty]=='#') continue;
		if(FF[tx][ty]=='D') continue;
		if(FF[tx][ty]=='S') continue;


		REP(j,8) if(dx[i]==rdx[j]&&dy[i]==rdy[j])
		{
			return j;
		}
	}

	return -1;
};

char refs[]={'/' , '\\' , '|' , '-' , 'O' };

bool isref(char c)
{
  REP(i,5) if(c==refs[i]) return true;

  return false;
}

bool laser[8][8];

bool Simulate(Field& f)
{
	bool ok[8][8]={0};
	bool v[8][8][8]={0};
	memset(laser,0,sizeof(laser));
	queue<LState> q;
	REP(i,H) REP(j,W)
	{
		if(FF[j][i]=='L')
			q.push(LState(j,i,LaserDir(f,j,i)));
	}

	bool bk=false;
	while(!q.empty())
	{
		LState Ls=q.front(); q.pop();
		if(v[Ls.x][Ls.y][Ls.d]) continue;
		v[Ls.x][Ls.y][Ls.d]=1;

		laser[Ls.x][Ls.y]=1;
		if(FF[Ls.x][Ls.y]=='S' && Ls.d%2==1) ok[Ls.x][Ls.y]=1;
		
		if(FF[Ls.x][Ls.y]=='D') bk=true;

		int tx=Ls.x+rdx[Ls.d], ty=Ls.y+rdy[Ls.d];
		if(tx<0||ty<0||tx>=W||ty>=H) continue;
		if(FF[tx][ty]=='*') continue;
		if(FF[tx][ty]=='#') continue;

		char type='!';
		if(islower(f.f[tx][ty])) type=Rtype[f.f[tx][ty]-'a'];

		if(type=='O')
		{
			pair<int, int> p=refcy(Ls.d);
			if(!v[tx][ty][p.first]) q.push(LState(tx,ty,p.first));
			if(!v[tx][ty][p.second]) q.push(LState(tx,ty,p.second));
		}
		else if(type=='/')
		{
			if(ref14(Ls.d)!=-1)
			{
				int td=ref14(Ls.d);
				if(v[tx][ty][td]) continue;
				q.push(LState(tx,ty,ref14(Ls.d)));
			}
		}
		else if(type=='\\')
		{
			if(ref34(Ls.d)!=-1)
			{
				int td=ref34(Ls.d);
				if(v[tx][ty][td]) continue;
				q.push(LState(tx,ty,ref34(Ls.d)));
			}
		}
		else if(type=='-')
		{
			if(refhor(Ls.d)!=-1)
			{
				int td=refhor(Ls.d);
				if(v[tx][ty][td]) continue;
				q.push(LState(tx,ty,refhor(Ls.d)));
			}
		}
		else if(type=='|')
		{
			if(refver(Ls.d)!=-1)
			{
				int td=refver(Ls.d);
				if(v[tx][ty][td]) continue;
				q.push(LState(tx,ty,refver(Ls.d)));
			}
		}
		else
		{
			if(v[tx][ty][Ls.d]) continue;
			q.push(LState(tx,ty,Ls.d));
		}
	}

	if(bk) return false;
	REP(i,Scnt) if(!ok[Sx[i]][Sy[i]]) return false;
	return true;
}

bool Move(int x, int y, Field fd, Flg flg, int mcnt, bool lmp[8][8], bool mv, bool ok, vector<Pos> ps)
{
	if(hg.count(mp(flg, ps))) return false;
	hg.insert(mp(flg, ps));

	bool g=ok, tlmp[8][8];
	memcpy(tlmp, lmp, sizeof(tlmp));
	//if(mv) 
	//{
		g=Simulate(fd);
		if(laser[x][y]) return false;
		
		memcpy(tlmp,laser,sizeof(tlmp));
	//}
	
	if(FF[x][y]=='D' &&  g) return true;
	

	REP(i,4)
	{
		Field tf=fd;
		vector<Pos> tps(ps);

		int tx=x+dx[i], ty=y+dy[i];
		int tmcnt=mcnt;
		Flg tflg = flg;
		bool fmv=false;

		if(tx<0||ty<0||tx>=W||ty>=H) continue;
		if(FF[tx][ty]=='*') continue;
		if(FF[tx][ty]=='S') continue;
		if(FF[tx][ty]=='L') continue;
		if(FF[tx][ty]=='#') continue;
		
		if(!islower(tf.f[tx][ty]) && tlmp[tx][ty])  continue;

		if(islower(fd.f[tx][ty]))
		{
			int ttx=tx+dx[i], tty=ty+dy[i];
			if(ttx<0||tty<0||ttx>=W||tty>=H) continue;
			if(FF[ttx][tty]=='*') continue;
			if(FF[ttx][tty]=='S') continue;
			if(FF[ttx][tty]=='L') continue;
			if(FF[ttx][tty]=='#') continue;
			if(FF[ttx][tty]=='D') continue;
			if(islower(fd.f[ttx][tty])) continue;

			Flg mv=tf.f[tx][ty]-'a';
			bool nw=!((tflg>>mv)&1);
			if(nw&&mcnt==2) continue;
			if(nw) 
			{
				tmcnt++;
				tps.push_back(mp(ttx,tty));
				

			}
			else
			{
				REP(i,tps.size())
					if(tps[i]==mp(tx,ty)) tps[i]=mp(ttx,tty);
			}
			
			tflg|= 1ULL << mv;
			tf.f[ttx][tty]=tf.f[tx][ty];
			
			fmv=true;
		}
		
		tps[0]=mp(tx,ty);

		tf.f[tx][ty]=tf.f[x][y];
		tf.f[x][y]='.';

		if(tmcnt==2)
		{
			if(tf.f[tps[1].first][tps[1].second]>tf.f[tps[2].first][tps[2].second])
				swap(tps[1],tps[2]);
		}

		if(Move(tx,ty,tf,tflg,tmcnt,lmp,fmv,g,tps)) return true;
	}

	return false;
}

int main()
{
	Scnt=0;
	Rcnt=0;
	cin >> W >> H;
	REP(i,H) REP(j,W)
	{
		cin >> FF[j][i];
		if(FF[j][i]=='@')
		{
			sx=j;
			sy=i;
		}
		if(isref(FF[j][i]))
		{
			Rtype[Rcnt]=FF[j][i];
			FF[j][i]=Rcnt+'a';
			Rcnt++;
		}

		if(FF[j][i]=='D')
		{
			gx=j;
			gy=i;
		}
		if(FF[j][i]=='S')
		{
			Sx[Scnt]=j;
			Sy[Scnt]=i;
			Scnt++;
		}
	}

	Field field(FF);
	vector<Pos> ps;
	ps.push_back(mp(sx,sy));
	cout << (Move(sx,sy,field,0,0,laser,true,false,ps)?"Yes":"No") << endl;
}