28511번 - Очерк 다국어

Художник Владимир, во время прогулки по осеннему саду, наблюдая за тем как огненно-рыжие листья падают с деревьев на поверхность сверкающих на солнце лужиц, и слушая пение птиц, которые уже совсем скоро покинут родные края, совершенно забыл, что ему завтра нужно сдавать проект.

Второпях Владимир нашёл какой-то компьютер, на котором он решил воссоздать набросок, который у нашего художника был в голове с точностью до пикселя. Вот только графический редактор, которым он решил воспользоваться, был крайне ограничен.

В этом графическом редакторе есть только две кисти --- одна в форме крестика, другая в виде нолика. Можно выбрать какую-то клетку $(x, y)$ ($1 \leqslant x \leqslant n$; $1 \leqslant y \leqslant m$) и одну из двух кистей. Тогда если была выбрана кисть-нолик, то будут покрашены в красный все клетки, у которых есть общая сторона с выбранной клеткой. Если же выбран крестик, то красными станут выбранная клетка и все, соседние с ней по углу.

Вам даётся набросок размера $n \times m$. Определите, может ли Владимир воссоздать его, используя только эти две кисти. Разрешается частью кисти выходить за границу рисунка.

В первой строке ввода через пробел даны два целых числа $n$ и $m$ --- размеры рисунка ($1 \leqslant n, m \leqslant 1000$).

В следующих $n$ строках вводится по $m$ символов --- символ равен <<*>>, если пиксель покрашен в красный, и <<.>>, если пиксель покрашен в белый.

Выведите ответ на задачу --- <<YES>> (без кавычек), если можно воссоздать рисунок, и <<NO>> в противном случае.

В первом тесте можем сделать два <<мазка>> в клетке $(3;4)$ --- один крестик, другой нолик.

Во втором тесте достаточно поставить нолик в клетке $(4;1)$ и в клетке $(5; 2)$. Разрешается кистью выходить за границы рисунка.