Jigglypuff

Time limit1sMemory limit512 MB

Summary

Given an n by m grid of letters, decide whether three distinct right-or-down paths from the top-left to the bottom-right can spell the same string.

Level: Medium7 of 10
Topics: String, String matching, Dynamic programming
Solved: No attempts yet

Problem

Your ACM team has gathered in the picturesque city of Petrozavodsk for a team-building camp. You have heard that just outside the city there is a Jigglypuff field that might help you build stronger bonds with your teammates, so you decided to give it a try.

The field is a rectangle divided into $n \times m$ squares, arranged in $n$ rows and $m$ columns. Each square holds one Jigglypuff, which produces a note when a team member steps on its cell. Each note is a single lowercase English letter.

You and your two teammates start at the top-left corner of the field and each walk to the bottom-right corner. You can move only right or down. Each of you must take a different route.

Jigglypuff have psychic abilities. If all three of you hear exactly the same sequence of notes, your brains synchronize perfectly and the team-building exercise is complete. Is this possible?

Input

The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 3000$ ), the height and width of the field. The following $n$ lines each contain a string of length $m$ made of lowercase English letters. The first character of the first line is the top-left corner of the field.

Output

Print YES if it is possible to hear the same sequence of notes on at least three different routes through the grid, or NO otherwise. Each letter may be printed in either case.

Hint

The picture below shows the first example test and three paths that produce the same sequence of notes, petrozavodsk:

Examples2

Example 1

Input

5 8
petrozav
eiiiziio
tiiiavid
riiiiois
ozavodsk

Expected output

YES

Example 2
Input
```
5 5
abcde
fghij
klmno
pqrst
uvwxy
```
Expected output
```
NO
```