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 CPP):

Solution:
/*  -*- coding: utf-8 -*-
 *
 * 1592.cc: Curling Puzzle
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 16;
const int MAX_W = 16;
const int WBITS = 1 << MAX_W;
const int MAX_N = MAX_H * MAX_W;
const int MAX_NN = MAX_N * MAX_N;
const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 };

/* typedef */

typedef queue<int> qi;

/* global variables */

char s[MAX_W + 4];
int xs[MAX_N], ys[MAX_N];
bool used[MAX_NN];

/* subroutines */

inline int xy2p(int x, int y) { return (y << 4) | x; }
inline void p2xy(int p, int &x, int &y) { x = p & 0xf; y = (p >> 4) & 0xf; }

inline int xy2p2(int x0, int y0, int x1, int y1) {
  int p0 = xy2p(x0, y0), p1 = xy2p(x1, y1);
  if (p0 > p1) swap(p0, p1);
  return (p0 << 8) | p1;
}

inline void p2xy2(int p2, int &x0, int &y0, int &x1, int &y1) {
  p2xy((p2 >> 8), x0, y0), p2xy((p2 & 0xff), x1, y1);
}

void move(int di, int &x0, int &y0, int x1, int y1, int w, int h) {
  const int &dx = dxs[di], &dy = dys[di];

  for (;;) {
    int x = x0 + dx, y = y0 + dy;
    if (x < 0 || x >= w || y < 0 || y >= h ||
	(x == x1 && y == y1)) break;
    x0 = x, y0 = y;
  }
}

/* main */

int main() {
  int h, w;
  scanf("%d%d", &h, &w);

  int gx, gy, n = 0;
  for (int y = 0; y < h; y++) {
    scanf("%s", s);
    for (int x = 0; x < w; x++) {
      if (s[x] == '@') gx = x, gy = y;
      else if (s[x] == 'o') xs[n] = x, ys[n] = y, n++;
    }
  }
  //printf("n=%d\n", n);

  if (n == 1) {
    if ((gx == xs[0] && (gy == 0 || gy == h - 1)) ||
	(gy == ys[0] && (gx == 0 || gx == w - 1)) ||
	((gx == 0 || gx == w - 1) && (gy == 0 || gy == h - 1))) {
      puts("yes");
      return 0;
    }
  }
  else if (h == 1 || w == 1) {
    if (w == 1) {
      w = h; gx = gy;
      memcpy(xs, ys, sizeof(ys));
    }

    int i1 = upper_bound(xs, xs + n, gx) - xs, i0 = i1 - 1;
    int x0 = (i0 >= 0) ? xs[i0] : -1;
    int x1 = (i1 < n) ? xs[i1] : w;
    if (x0 + (n - 1 - i0) >= gx || x1 - i1 <= gx) {
      puts("yes");
      return 0;
    }
  }
  else if (n == 2) {
    int st = xy2p2(xs[0], ys[0], xs[1], ys[1]);
    used[st] = true;
    qi q;
    q.push(st);

    while (! q.empty()) {
      int u = q.front(); q.pop();
      int ux0, uy0, ux1, uy1;
      p2xy2(u, ux0, uy0, ux1, uy1);
      if ((ux0 == gx && uy0 == gy) || (ux1 == gx && uy1 == gy)) {
	puts("yes");
	return 0;
      }

      for (int di = 0; di < 4; di++) {
	int x = ux0, y = uy0;
	move(di, x, y, ux1, uy1, w, h);
	int v0 = xy2p2(x, y, ux1, uy1);
	if (! used[v0]) {
	  used[v0] = true;
	  q.push(v0);
	}

	x = ux1, y = uy1;
	move(di, x, y, ux0, uy0, w, h);
	int v1 = xy2p2(x, y, ux0, uy0);
	if (! used[v1]) {
	  used[v1] = true;
	  q.push(v1);
	}
      }
    }
  }
  else {
    puts("yes");
    return 0;
  }

  puts("no");
  return 0;
}