Дана таблица \(n \times m\) из белых и черных клеток. За одну операцию можно выбрать две клетки одного цвета и покрасить в этот цвет все клетки в подпрямоугольнике между ними.
Формально, если выбрать позиции \((x_1, y_1)\) и \((x_2, y_2)\), которые в данный момент имеют цвет \(c\), установите цвет всех \((x, y)\), где \(\min(x_1, x_2) \le x \le \max(x_1, x_2)\) и \(\min(y_1, y_2) \le y \le \max(y_1, y_2)\) в \(c\).
На этой диаграмме показана последовательность двух возможных операций в таблице:
Возможно ли, чтобы все клетки в таблице были одного цвета после выполнения любого количества операций (возможно, нуля)?
Выходные данные
Для каждого теста выведите «YES», если возможно сделать все клетки в таблице одного цвета, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (верхний или нижний). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом примере невозможно изменить цвет любой клетки с помощью операции, поэтому мы выводим NO.
Во втором примере это случай, изображенный выше. Как показано на этой диаграмме, возможно, что все клетки будут белыми после двух операций, поэтому мы выводим YES.
В третьем и четвертом примерах все клетки уже имеют одинаковый цвет, поэтому мы выводим YES.
В пятом примере мы можем сделать все за две операции. Сначала выберем позиции \((2, 1)\) и \((1, 4)\) и покрасим все клетки с \(1 \le x \le 2\) и \(1 \le y \le 4\) в белый цвет. Затем выберем позиции \((2, 1)\) и \((3, 4)\) и покрасим все клетки с \(2 \le x \le 3\) и \(1 \le y \le 4\) в белый цвет. После этих двух операций все клетки будут белыми.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2 1
W
B
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
1 1
W
2 2
BB
BB
3 4
BWBW
WBWB
BWBW
4 2
BB
BB
WW
WW
4 4
WWBW
BBWB
WWBB
BBBB
1 5
WBBWB
|
NO
YES
YES
YES
YES
NO
YES
NO
|