Stamps

Little Johnny draws pictures on a square sheet of paper of size $k \times k$, divided into unit cells. At the start the whole sheet is white.

He owns a small magic stamp shaped like a $3 \times 3$ square of unit cells, exactly two of which are raised. Those two raised cells always lie in the same row or in the same column. To use the stamp he presses it onto the sheet so that its raised cells cover cells of the sheet exactly; every cell touched by a raised cell flips its colour (white becomes black and black becomes white). The stamp may hang partially off the sheet, but both raised cells must always land inside the sheet. The stamp can be translated freely but never rotated.

Johnny may also use a big magic stamp of size $s \times s$ with an arbitrary set of raised cells (they need not share a row or a column). It flips colours in the same way, but it may be pressed only when the whole $s \times s$ stamp lies completely inside the sheet.

A target picture is given as the set of cells that must end up black (every other cell must end up white). Given the two stamps and a target picture, decide whether the picture can be produced from the all-white sheet using any sequence of presses of the two stamps together.

The first line contains an integer $t$ ($1 \le t \le 10$): the number of test cases.

Each test case begins with a line containing two integers $s$ and $k$ ($1 \le s \le k \le 1000$, $1 \le s \le 200$): the side length of the big stamp and the side length of the sheet.

The next three lines describe the small stamp as a $3 \times 3$ grid of the characters 0 and 1. The grid shows how a white sheet looks after one press of the small stamp: 1 marks a cell that was flipped to black, 0 a cell that stays white. Exactly two characters are 1, and they lie in the same row or the same column. (The grid shows the imprint left on the paper, which is the mirror image of the raised pattern of the physical stamp.)

The next $s$ lines describe the big stamp in the same format, as an $s \times s$ grid of 0 and 1; here any number of cells may be 1.

The next $k$ lines describe the target picture as a $k \times k$ grid, where 1 is a cell that must be black and 0 a cell that must be white.

For each test case output a single line: TAK (Polish for "yes") if the target picture can be drawn using the two stamps together, or NIE (Polish for "no") otherwise.

In the test data, the picture Johnny is trying to draw need not resemble an actual bunny.