Tic-Tac-Toe

Time limit2sMemory limit1024 MB

Summary

Given an n by m board of X, O, and empty cells, the task is to check whether any row, column, or diagonal has five identical marks in a row.

Level: Easy3 of 10
Topics: Matrix, Implementation
Solved: No attempts yet

Statement

One day, while walking through King's Landing, Lord Petyr Baelish found a sheet of squared paper covered in strange symbols. Someone had played tic-tac-toe on it.

Lord Baelish knows the rules well. Players take turns, and each one places a mark in any free cell. One player places an X and the other places an O. He does not know who played this game, but he wants to know whether it is finished. A game is finished if there is a horizontal, vertical, or diagonal line of five X or O symbols. The position may be invalid, and Baelish does not care about that.

Write a program that determines whether the game is finished.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 1000$ ), the dimensions of the board.

Each of the next $n$ lines contains $m$ characters. Each character is X, O, or ., meaning the cell holds an X, holds an O, or is empty. X and O are uppercase Latin letters.

Output

Print Yes if the game is finished, and No otherwise.

Examples1

Example 1

Input

5 6
.OXOXO
OXX.O.
XXOOXX
..O..O
OOXX.X

Expected output

Yes