C. Saki and Separation
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The unified class is hosting a cantus tournament where classes A and B advanced to the final. However, during the final match, there was an accident where the cantus of the students are entangled together. Saki is tasked with dealing with this situation as soon as possible.

The students are located in an infinite grid, where the rows and columns are numbered with integers. The cell at the $$$i$$$-th row and $$$j$$$-th column is represented as $$$(i, j)$$$, and it is known that all the students occupy a distinct cell, and their location satisfy $$$0 \le i \lt N$$$ and $$$0 \le j \lt M$$$.

Saki will attempt to separate class A and B students from each other, if possible. In one move, she can pick either class A or B, and order every student in that class to simultaneously move one cell in one of four directions: right, up, left, or down. She cannot perform the move if it would result in a student from class A and a student from class B being in the same cell.

Write a program to help Saki determine if it is possible to separate class A and B. They are considered separated if the smallest euclidean distance between a student from class A and a student from class B is at least $$$10^{9999999999999999999999}$$$.

Input

The input is given in the following format:

$$$N$$$$$$M$$$
$$$S_0$$$
$$$\vdots$$$
$$$S_{N-1}$$$

where

  • $$$N$$$ is the upper bound of the row number of students,
  • $$$M$$$ is the upper bound of the column number of students,
  • and $$$S_i$$$ is a string of length $$$M$$$ where the $$$j$$$-th character is "." if there is no student at the cell $$$(i, j)$$$, otherwise it is "A" or "B" depending on from which class the student is from.

The input satisfies the following constraints:

  • $$$N$$$ and $$$M$$$ are integers.
  • $$$2 \le N, M \le 1000$$$.
  • There is at least one "A" and "B" in the input.
Output

If it is possible to separate them, print a single line containing the string "Yes", otherwise print a single line containing the string "No". You may print each character in either case (lower or upper).

Examples
Input
4 5
AAAA.
ABBBB
AAAAB
.BBBB
Output
Yes
Input
3 4
.AA.
AB.A
.AA.
Output
No