#P9971. Three-step Chess

    ID: 23115 Type: Default 1000ms 256MiB

Three-step Chess

Three-step Chess

In the game of Three-step Chess, two players (named K and H) take turns placing identical pieces on a 5×5 grid. Prior to the game, a specific pattern is chosen. This pattern is a four-connected shape consisting of at most 4 pieces, represented by the character o (empty cells are denoted by .). The pattern is not allowed to be rotated when checking for its occurrence on the board.

The rules of the game are as follows:

  1. Both players place the same kind of piece (i.e. there is no distinction between the pieces).
  2. After each move, the board is checked to see if the selected pattern appears somewhere on the board exactly as given (i.e. with the same orientation and relative positions).
  3. If the pattern is formed right after a move, let N be the total number of pieces on the board. If N is a multiple of 3, then the player who just placed the piece wins. Otherwise, that move is considered a losing move and the opponent is declared the winner.

Note that since the game ends as soon as a pattern is formed (and the win/loss condition is applied), there will be no drawn games. In fact, if both players play optimally, the outcome (win or loss for the first mover) is completely determined by the given pattern. In this problem, you are asked to decide whether the game with the chosen pattern is a forced win for the first player.

The game always starts on an initially empty 5×5 board.

inputFormat

The first line contains two integers r and c (1 ≤ r, c ≤ 4), representing the number of rows and columns of the designated pattern. The next r lines each contain a string of length c consisting of characters o and . describing the pattern. It is guaranteed that the cells marked with o form a four-connected set.

outputFormat

Output a single line containing Yes if the first player can force a win under optimal play, or No otherwise.

sample

1 1
o
No