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<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;

int H,W,LP,LP_dir;
bool polluted_room[9][9];
bool visited[9][9];
char room[9][9];
int dx8[] = {+0,+1,+1,+1,+0,-1,-1,-1};//0   1    2  3     4  5    6   7
int dy8[] = {-1,-1,+0,+1,+1,+1,+0,-1};//上、右上、右、右下、下、左下、左、左上
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<int> statue;

inline bool isMirror(int x,int y) { 
  return ( room[y][x] == '/' || room[y][x] == '\\' || room[y][x] == '-' || room[y][x] == '|' || room[y][x] == 'O' );
}
inline bool isValid(int x,int y) { return 0 <= x && x < W && 0 <= y && y < H; }
inline bool validMove(int x,int y,int dir) {
  if( room[y][x] == '#' || room[y][x] == '*' || room[y][x] == 'S' || room[y][x] == 'L' || room[y][x] == 'D') return false;
  if( isMirror(x,y) ) {
    int nx = x + dx[dir], ny = y + dy[dir];
    if( !isValid(nx,ny) ) return false;
    if( room[ny][nx] != '.' ) return false;
  }
  return true;
}

//現在のマップでうるるビームを撃つ
//れーざーが循環している場合に注意すること

void UruruBeam(int sp,int sp_dir){
  rep(i,H) rep(j,W) polluted_room[i][j] = false;
  deque<ii> deq;
  deq.push_back(ii(sp,sp_dir));
  polluted_room[sp/W][sp%W] = true;
  set<ii> S;
  S.insert(ii(sp,sp_dir));
  while( !deq.empty() ){
    ii tmp = deq.front(); deq.pop_front();
    int x = tmp.first % W, y = tmp.first / W, dir = tmp.second;

    while( 1 ){
      x += dx8[dir], y += dy8[dir];

      if( !isValid(x,y) ) break;
      polluted_room[y][x] = true;
      if( room[y][x] == '#' || room[y][x] == '*' || room[y][x] == 'D' || room[y][x] == 'L' ) break;
      if( room[y][x] == 'S' ) {
        if( dir & 1 ) polluted_room[y][x] = false;
        break;
      }

      if( room[y][x] == '/' ) {
        if( dir == 1 || dir == 5 ) break;
        int next_dir = -1;
        if( dir == 0 ) next_dir = 2;
        else if( dir == 2 ) next_dir = 0;
        else if( dir == 3 ) next_dir = 7;
        else if( dir == 4 ) next_dir = 6;
        else if( dir == 6 ) next_dir = 4;
        ii next = ii(x+y*W,next_dir);
        if( S.count(next) ) break;
        S.insert(next);
        deq.push_back(next);
        break;
      } else if( room[y][x] == '\\' ) {
        if( dir == 3 || dir == 7 ) break;
        int next_dir = -1;
        if( dir == 0 ) next_dir = 6;
        else if( dir == 1 ) next_dir = 5;
        else if( dir == 2 ) next_dir = 4;
        else if( dir == 4 ) next_dir = 2;
        else if( dir == 5 ) next_dir = 1;
        else if( dir == 6 ) next_dir = 0;
        ii next = ii(x+y*W,next_dir);
        if( S.count(next) ) break;
        S.insert(next);
        deq.push_back(next);
        break;
      } else if( room[y][x] == '-' ) {
        if( dir == 2 || dir == 6 ) break;
//0   1    2   3     4  5     6   7
//上、右上、右、右下、下、左下、左、左上
        int next_dir = -1;
        if( dir == 0 ) next_dir = 4;
        else if( dir == 1 ) next_dir = 3;
        else if( dir == 3 ) next_dir = 1;
        else if( dir == 4 ) next_dir = 0;
        else if( dir == 5 ) next_dir = 7;
        else if( dir == 7 ) next_dir = 5;
        ii next = ii(x+y*W,next_dir);
        if( S.count(next) ) break;
        S.insert(next);
        deq.push_back(next);
        break;
      } else if( room[y][x] == '|' ) {
        if( dir == 0 || dir == 4 ) break;
        int next_dir = -1;
        if( dir == 1 ) next_dir = 7;
        else if( dir == 2 ) next_dir = 6;
        else if( dir == 3 ) next_dir = 5;
        else if( dir == 5 ) next_dir = 3;
        else if( dir == 6 ) next_dir = 2;
        else if( dir == 7 ) next_dir = 1;
        ii next = ii(x+y*W,next_dir);
        if( S.count(next) ) break;
        S.insert(next);
        deq.push_back(next);
        break;
      } else if( room[y][x] == 'O' ) {
        ii next[2] = {ii(x+y*W,-1),ii(x+y*W,-1)};
        if( dir == 0 ) next[0].second = 1, next[1].second = 7;
        else if( dir == 1 ) next[0].second = 0, next[1].second = 2;
        else if( dir == 2 ) next[0].second = 1, next[1].second = 3;
        else if( dir == 3 ) next[0].second = 2, next[1].second = 4;
        else if( dir == 4 ) next[0].second = 3, next[1].second = 5;
        else if( dir == 5 ) next[0].second = 4, next[1].second = 6;
        else if( dir == 6 ) next[0].second = 7, next[1].second = 5;
        else if( dir == 7 ) next[0].second = 0, next[1].second = 6;
        rep(_i,2) {
          if( !S.count(next[_i]) ) {
            S.insert(next[_i]);
            deq.push_back(next[_i]);
          }
        }
        break;
      }

    }

  }
}

//現状でゴールに到達可能か判定, この関数を呼ぶ前にうるるビームを発射してpolluted_roomを作成しておくこと
bool solved(int sp){
  rep(i,(int)statue.size()) if( !polluted_room[statue[i]/W][statue[i]%W] ) return false;
  rep(i,H) rep(j,W) visited[i][j] = false;
  deque<int> deq;
  deq.push_back(sp);
  visited[sp/W][sp%W] = true;
  while( !deq.empty() ){
    int cur = deq.front(); deq.pop_front();
    if( polluted_room[cur/W][cur%W] ) continue;
    if( room[cur/W][cur%W] == 'D' ) return true;
    rep(i,4) {
      int nx = cur % W + dx[i], ny = cur / W + dy[i];
      if( !isValid(nx,ny) ) continue;
      if( !( room[ny][nx] == '.' || room[ny][nx] == 'D' ) ) continue; // 鏡を動かしてゴールできる場合はまた別、再帰でみつけるべし
      if( polluted_room[ny][nx] || visited[ny][nx] ) continue;
      visited[ny][nx] = true;
      deq.push_back(nx+ny*W);
    }
  }
  return false;
}

/* 
   前の方向に戻らないようにするだけ ( 鏡を動かした場合はアリです！ )
   or
   （メモリに余裕があるなら) setに動けるやつの状態積めて枝刈り
 */

typedef pair<int,vector<int> > ivi;
set<ivi> S;
//typedef pair<int,deque<int> > idi;
//set<idi> S;
bool BackTracking(int cur,int prev,deque<int> &deq){

  if( !deq.empty() ) sort(deq.begin(),deq.end());
  vector<int> tmper;
  rep(i,deq.size()) tmper.push_back(deq[i]*1000+room[deq[i]/W][deq[i]%W]);
  if( S.count(ivi(cur,tmper)) ) return false;
  S.insert(ivi(cur,tmper));

  /*
  vector<int> tmper;
  rep(i,H) rep(j,W) if( isMirror(j,i) ) tmper.push_back((j+i*W)*1000+room[i][j]);
  sort(tmper.begin(),tmper.end());
  if( S.count(ivi(cur,tmper)) ) return false;
  S.insert(ivi(cur,tmper));
  */
  /*
  cout << endl;
  cout << "(" << cur%W << "," << cur/W << ")" << endl;
  rep(i,H) {
    rep(j,W) {
      if( j == cur%W && i == cur/W ) cout << "@";
      else
      cout << room[i][j];

    }
    puts("");
  }
  */
  UruruBeam(LP,LP_dir);
  /*
  rep(i,H) {
    rep(j,W) cout << polluted_room[i][j];
    puts("");
  }
  */
  if( polluted_room[cur/W][cur%W] ) return false; // dead
  if( solved(cur) ) return true;
  rep(i,4){
    if( prev == (i+2) % 4 ) continue;
    int nx = cur % W + dx[i], ny = cur / W + dy[i];
    if( !isValid(nx,ny) ) continue;
    //if( polluted_room[ny][nx] ) continue;
    if( !validMove(nx,ny,i) ) continue;
    bool mirror = false;
    int new_one = -1;
    if( isMirror(nx,ny) ) {
      rep(j,deq.size()) if( deq[j]%W == nx && deq[j]/W == ny ) {
        new_one = j;
        break;
      }
      if( new_one == -1 && deq.size() == 2 ) continue;

      assert(room[ny+dy[i]][nx+dx[i]] == '.');
      if( new_one == -1 ) deq.push_back((nx+dx[i])+(ny+dy[i])*W);
      else                deq[new_one] = (nx+dx[i])+(ny+dy[i])*W;
      room[ny+dy[i]][nx+dx[i]] = room[ny][nx]; // 鏡蓮児が連続していた場合それらは全て動かせるのか??? 
      room[ny][nx] = '.';
      mirror = true;
      UruruBeam(LP,LP_dir);
      if( polluted_room[ny][nx] ) goto Skip;
    } 
    if( !mirror && polluted_room[ny][nx] ) continue;
    if( BackTracking(nx+ny*W,(mirror?-1:i),deq) ) return true;

  Skip:;
    if( mirror ) {
      assert( isMirror(nx+dx[i],ny+dy[i]) );
      room[ny][nx] = room[ny+dy[i]][nx+dx[i]];
      room[ny+dy[i]][nx+dx[i]] = '.';
      if( new_one == -1 ) {
        rep(j,deq.size()) if( deq[j] == (nx+dx[i])+(ny+dy[i])*W ) {
          deq.erase(deq.begin()+j);
          break;
        }
      } else {
        rep(j,deq.size()) if( deq[j] == (nx+dx[i])+(ny+dy[i])*W ) {
          deq[j] = nx + ny * W;
          break;
        }
      }
    }
  }
  return false;
}

/*
 初期で死んでいる場合
 初期でゴールできる場合 に注意
 */
int main(){
  LP = LP_dir = -1;
  int sp = -1;
  cin >> W >> H;
  rep(i,H) rep(j,W) {
    cin >> room[i][j];
    if( room[i][j] == '@' ) sp = j + i * W,room[i][j] = '.';
    if( room[i][j] == 'L' ) { assert( LP == -1); LP = j + i * W; }
    if( room[i][j] == 'S' ) statue.push_back(j+i*W);
  }
  for(int k=0;k<8;k+=2) {
    int nx = LP%W + dx8[k], ny = LP/W + dy8[k];
    if( !isValid(nx,ny) ) continue;
    if( nx == 0 || ny == 0 || nx == W-1 || ny == H-1 ) continue;
    LP_dir = k;
  }
  assert( LP_dir != -1 );


  UruruBeam(LP,LP_dir);
  /*
  rep(i,H){
    rep(j,W){
      cout << polluted_room[i][j];
    }
    cout << endl;
  }
  cout << solved(sp) << endl;
  return 0;
  */
  if( polluted_room[sp/W][sp%W] ) {
    puts("No");
    return 0;
  }
  if( solved(sp) ) {
    puts("Yes");
    return 0;
  }
  deque<int> deq;
  puts(BackTracking(sp,-1,deq)?"Yes":"No");
  return 0;
}

/*
重要 : But he can push up to two of mirrors/crystals because the door will be locked forever when he pushes the third mirrors/crystals.
何度でもミラーorクリスタルを動かせるが、ただしそれは２つまで
 */