Ennichi

Time limit1sMemory limit512 MB

Summary

On a grid with falling blocks, decide whether one swap of two horizontally adjacent cells can trigger chain reactions that clear every block.

Level: Medium7 of 10
Topics: Simulation, Implementation, Brute force, BFS
Solved: No attempts yet

Problem

A rabbit visiting a festival finds that the prize of a stall game is a carrot cake. The rules of the game are as follows.

There is a grid field with $h$ rows and $w$ columns, and each cell holds at most one block. Each block has a color represented by one uppercase letter ('A' to 'Z'). When $n$ or more blocks of the same color line up consecutively in a straight line vertically or horizontally, those blocks disappear.

The player can choose two horizontally adjacent cells and swap their states with each other. If a swap, a disappearance, or a fall leaves the cell directly below a cell that has a block empty, that block falls. If $n$ or more blocks of the same color line up again at that point, they disappear. However, blocks do not disappear while any block is falling; all disappearances happen at once when every block has finished falling.

If the player clears every block on the field with one move, the game is a success and the player wins the cake prize. The rabbit wants to be certain of getting the cake for one entry fee, and does not want to play if that is impossible. Starting from the field state at the beginning of the game, answer whether the rabbit should play this game.

Input

The first line of input gives $h$ , $w$ , and $n$ , separated by spaces.

$2 \le h, w, n \le 30$

The next $h$ lines give the field state from top to bottom. An uppercase letter represents a block, and '.' represents an empty cell. The given field state has no run of $n$ or more blocks of the same color vertically or horizontally, and no block is in a falling state. There is at least one block.

Output

If the rabbit should play this game, print "YES"; otherwise, print "NO", on one line.

Examples2

Example 1
Input
```
4 6 3
......
...Y..
...Y..
RRYRYY
```
Expected output
```
YES
```
Example 2
Input
```
4 6 3
......
...Y..
...Y..
RRYRY.
```
Expected output
```
NO
```