Jedi(500)

It's the time of the First Order's uprising. The evil Kylo Ren wants to find a map that leads to the Resistance's hero, Luke Skywalker. Kylo Ren currently has an incomplete map, a matrix of size N*M filled with star systems which are rectangles filled with #. An R*S portion of the map is cut out; that part is covered with ! in the input.

Kylo Ren currently has Q possible matrixes that represent the cut out part of the map, and as he has some work to do in getting Tie/SF Fighters he asks you for help. For each possible matrix you have to determine whether the map is correct. A correct map is one where no 2 star systems share an edge and all # are a part of exactly 1 star system.