Painting the wall

Problem Statement

Painting the wall You are a painter. A wall is an N x M grid of cells. A cell written O is plain wall and must be painted; a cell written X is a window and must never receive paint. Your brush covers an axis-aligned rectangle of X rows by Y columns, and you may also turn it ninety degrees and use it as Y rows by X columns. A single stroke places the brush over a rectangle of cells, and a stroke is allowed only when the whole rectangle lies inside the wall and contains no window at all. You may make as many strokes as you like and they may overlap freely; repainting a cell is harmless. For each wall, decide whether every O cell can be painted. Input Format The first line contains a single integer T -- the number of walls. Each wall is given as follows: a line with four integers N , M , X and Y -- the wall's rows and columns, then the brush's rows and columns; N lines of exactly M characters each, every character either O or X . Output Format For each wall print one line: YES if every O