G. Space Invaders
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A certain species of space invaders were found on the streets of Paris, taking a mosaic form. Each invader has a fixed shape represented by the following $$$8 \times 13$$$ pattern:

#..#..#..#..#
#.#########.#
###.#####.###
###.#####.###
#####...#####
..#########..
..###...###..
.##....##....

Each # denotes an occupied cell, and each . denotes empty cell.

For a positive integer $$$k$$$, a scaled invader is obtained by replacing every cell of the pattern with a $$$k \times k$$$ block. Occupied cells become filled $$$k \times k$$$ blocks, and empty cells become empty $$$k \times k$$$ blocks.

You want to code an «invader detector». Your program will be given a photo of a grid that may or may not contain space invaders. You need to determine if there exists such configuration of space invaders that:

  • There is at least one space invader.
  • Every occupied cell belongs to exactly one space invader,
  • All space invaders have the same scale $$$k$$$,
  • It is allowed for one space invader's occupied cells to overlap with empty cells of another space invader.
Input

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

Each of the next $$$n$$$ lines contains a row of a grid, that has exactly $$$m$$$ characters, each being "#" or ".", that represent occupied or empty cell correspondingly.

Output

Print YES if the photo is valid, otherwise print NO.

Examples
Input
8 13
#..#..#..#..#
#.#########.#
###.#####.###
###.#####.###
#####...#####
..#########..
..###...###..
.##....##....
Output
YES
Input
4 5
.#.#.
#.#.#
.#.#.
#.#.#
Output
NO
Input
8 30
..#..#..#..#..#..#..#..#..#..#
..#.#########.#..#.#########.#
..###.#####.###..###.#####.###
..###.#####.###..###.#####.###
..#####...#####..#####...#####
....#########......#########..
....###...###......###...###..
...##....##.......##....##....
Output
YES
Input
9 16
#######..#######
##.......#######
##...........##.
##..........##..
######.....##...
#######...##....
##...##..##.....
##...##.##......
#########.......
Output
NO
Note

The first sample matches the space invader pattern with scaling parameter $$$k=1$$$.

Please note the constraints of the problems are quite IO heavy. Jury's Python solution uses 

sys.stdin.buffer.read().split()
and stores the grid in one dimensional arrays.