F. 800
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Oussama, Rami and Yessine were travelling to Egypt in order to participate in a programming contest. Unfortunately, the plane crushed in some unknown island and everyone died except the three of them. They spent the next few months eating coconuts and sleeping on the sands. One day, Yessine found a bottle on the beach. Inside the bottle there was a letter. They found the number $$$800$$$ written on the back of paper so they were curious about it so they started reading the letter. They were shocked to find out that the letter contained some hard problem. Oussama got angry and decided to burn the paper but Rami was really curious about the number $$$800$$$, and he decided to solve it hoping that he might find an explanation. The problem says: You are given a grid of lowercase characters 'a'-'z'. You can do the following operation any number of times :

  • choose a cell $$$(i,j)$$$ and a positive integer $$$k,$$$ and change the content of the cell $$$(i-k,j-k)$$$ or $$$(i-k,j+k)$$$ to that of $$$(i,j)$$$.
Given a character $$$C$$$, can you make the grid composed only of $$$C$$$?

Rami's stomach hurts from eating too much coconuts so he can't think properly, help him solve the problem.

Input
  • The first line of the input contains $$$1 \leq N \leq 10^3$$$ and $$$1 \leq M \leq 10^3$$$: the dimensions of the grid
  • The Second line contains the character $$$C$$$
  • Next $$$N$$$ lines contain each $$$M$$$ characters. the $$$j$$$th character on the $$$i$$$th line denotes the character at cell($$$i$$$,$$$j$$$).
Output

print a single line containing YES if you can or NO if you can't.

Examples
Input
3 3
b
aaa
aaa
aaa
Output
NO
Input
1 1
a
a
Output
YES
Note

Note that the top left cell of the grid is $$$(0,0).$$$ And the cell $$$(N-1,M-1)$$$ is the one on the bottom right..