Eles T99685

Statement

Teniu un tauler $n \times m$ amb caselles lliures i caselles ocupades. Disposeu d’un nombre ilimitat de rajoles en forma de lletra L, les quals es poden posar tal qual, o girades 180 graus. És possible cobrir totes les caselles lliures del tauler, sense que les rajoles se suporposin, surtin fora del tauler, ni tapin caselles ja ocupades?

Aquest dibuix es correspon al primer cas de l’Exemple d’entrada. En verd s’han pintat les rajoles posades rectes, i en vermell les girades. No es poden posar eles d’altres mides, ni girades de cap altra manera.

(16,10) (2,2)(2,8)(4,8)(4,4)(6,4)(6,2) (10,2)(10,8)(12,8)(12,4)(14,4)(14,2)

(10,10)(14,10)(14,4)(12,4)(12,8)(10,8) (4,8)(8,8)(8,2)(6,2)(6,6)(4,6)

(0,0)(0,10) (2,0)(2,10) (4,0)(4,10) (6,0)(6,10) (8,0)(8,10) (10,0)(10,10) (12,0)(12,10) (14,0)(14,10) (16,0)(16,10) (0,0)(16,0) (0,2)(16,2) (0,4)(16,4) (0,6)(16,6) (0,8)(16,8) (0,10)(16,10)

(1,1) (1,3) (1,5) (1,7) (1,9) (3,1) (3,9) (5,1) (5,5) (5,9) (7,1) (7,9) (9,1) (9,3) (9,5) (9,7) (9,9) (11,1) (13,1) (15,1) (15,3) (15,5) (15,7) (15,9)

Entrada

L’entrada conté diversos casos, cadascun amb $n$ i $m$ , seguides d’ $n$ files amb $m$ caràcters cadascuna. Els punts indiquen caselles lliures, i les ‘X’ caselles ocupades. Podeu suposar $3 \le n \le 1000$ , $2 \le m \le 1000$ , i que el nombre de caselles lliures és múltiple de quatre.

Sortida

Per a cada cas, escriviu “si” o “no” segons convingui.

Public test cases

Input

5 8
XXXXX..X
X...X..X
X.X.X..X
X...X..X
XXXXXXXX

3 3
.X.
...
...

3 2
.X
.X
..

Output

si
no
si

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++