Problem: Problem

There is a puzzle game where you move curling stones and stack them exactly on the goal square. The detailed rules are as follows.

The field consists of H × W squares, with stones placed in some squares at the beginning. There is only one goal square, and no stone is placed on the goal square from the beginning. In addition, the field is surrounded by an outer wall, so stones will not jump out of the field on the way.

Players can choose one stone for each move and launch it in either the up, down, left, or right direction to slide it. A slipping stone will continue to slide until it hits another stone or the outer wall of the field. If it hits another stone, the stone on the hit side will be recoiled and will slide in a chain in the same direction as the first shot.

For example, when stone A is launched to the right in the state of FIG. 1, the final state is as shown in FIG.

Figure 1


Figure 1





Figure 2


Figure 2





The condition for clearing this puzzle is to place one of the stones on the field exactly on the goal square. It will not be cleared if you pass the goal square.

Your job is to create a program that takes the initial state of the field as input and outputs whether the puzzle is clear or not.

Constraints

* 1 ≤ H ≤ 16
* 1 ≤ W ≤ 16
* 2 ≤ H x W ≤ 256
* Guaranteed to have only one goal square
* Guaranteed to have at least one square with curling stones on it

Input

The input is given in the following format.


H W
F11 F12 ... F1W
F21 F22 ... F2W
...
FH1 FH2 ... FHW


Fij is either'.',' O', or'@', and each has the following meaning. (1 ≤ i ≤ H, 1 ≤ j ≤ W)

*'.': Blank cell
*'o': The square on which the curling stone is placed
*'@': Goal square

Output

Print "yes" or "no" (not including "") on one line to see if the puzzle is clear.

Examples

Input

1 10
o........@


Output

yes


Input

3 6
......
.o..@.
......


Output

no


Input

6 4
....
.oo.
.oo.
....
.@..
....


Output

yes

Solution (in JAVA):

Solution:
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static long startTime = System.currentTimeMillis();
	static final int[] DR = { 1, 0, -1, 0 };
	static final int[] DC = { 0, 1, 0, -1 };
	static int H, W, gr, gc;
	static char[][] F;

	public static void main(String[] args) {
		H = sc.nextInt();
		W = sc.nextInt();
		F = new char[H][];
		int stone = 0;
		for (int i = 0; i < H; ++i) {
			F[i] = sc.next().toCharArray();
			for (int j = 0; j < W; ++j) {
				if (F[i][j] == 'o') {
					++stone;
				} else if (F[i][j] == '@') {
					gr = i;
					gc = j;
				}
			}
		}
		boolean ans;
		if (stone >= 3) {
			if (H > 1 && W > 1) {
				ans = true;
			} else {
				ans = search();
			}
		} else if (stone == 2) {
			if (H > 1 && W > 1 && (gr == 0 || gr == H - 1 || gc == 0 || gc == W - 1)) {
				ans = true;
			} else {
				ans = search();
			}
		} else {
			ans = search();
		}
		System.out.println(ans ? "yes" : "no");
	}

	static boolean search() {
		HashSet<ArrayList<Point>> cur = new HashSet<>();
		ArrayList<Point> init = new ArrayList<>();
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (F[i][j] == 'o') init.add(new Point(j, i));
			}
		}
		cur.add(init);
		OUT: for (int i = 0;; ++i) {
			HashSet<ArrayList<Point>> next = new HashSet<>();
			for (ArrayList<Point> st : cur) {
				if (System.currentTimeMillis() - startTime > 900) {
					break OUT;
				}
				for (Point p : st) {
					for (int dir = 0; dir < 4; ++dir) {
						ArrayList<Point> moved = new ArrayList<>();
						Point mp = null;
						for (Point np : st) {
							moved.add(new Point(np.x, np.y));
							if (np.equals(p)) mp = moved.get(moved.size() - 1);
						}
						while (true) {
							int nx = mp.x + DC[dir];
							int ny = mp.y + DR[dir];
							if (nx < 0 || nx >= W || ny < 0 || ny >= H) {
								if (mp.x == gc && mp.y == gr) return true;
								break;
							}
							for (Point np : moved) {
								if (np == mp) continue;
								if (np.x == nx && np.y == ny) {
									if (mp.x == gc && mp.y == gr) return true;
									mp = np;
									break;
								}
							}
							mp.x = nx;
							mp.y = ny;
						}
						//						System.out.println(moved);
						Collections.sort(moved, (Point p1, Point p2) -> {
							if (p1.x != p2.x) return Integer.compare(p1.x, p2.x);
							return Integer.compare(p1.y, p2.y);
						});
						next.add(moved);
					}
				}
			}
			cur = next;
		}
		return false;
	}

}