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.
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.
You can assume the following conditions:
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.
Figure 4 is one of the solution for the first sample 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:
The judges also guarantee that this problem can be solved without extraordinary optimizations.
Output "Yes" if it is possible for him to leave the room. Otherwise, output "No".
7 8 ##S#### #.....# S.O...# #.*|..# L..*..# #.O*..D #.@...# #######
Yes
8 3 ###L#### S.../@.# ######D#
Yes
8 3 ##L##### S..\.@.# ######D#
No