Description

On an $n\times m$ grid paper, some cells should be stamped black, and the remaining cells should be left white.

You have an $a\times b$ stamp in which some cells are raised (will pick up ink). Determine whether you can use this stamp to produce the pattern on the paper, under the following rules:

1. The stamp cannot be rotated.
2. You cannot stamp outside the paper.
3. No cell on the paper may be stamped more than once.

Input Format

The first line contains an integer $q$ ($1\leq q\leq 10$), the number of test cases.

Then for each of the $q$ test cases:

• The first line contains $4$ integers $n, m, a, b$ ($1\leq n, m, a, b\leq 10^3$).
• The next $n$ lines, each with $m$ characters, describe the target pattern on the paper. . means blank, x means black.
• The next $a$ lines, each with $b$ characters, describe the stamp. . means not inked, x means inked.

Output Format

For each test case, output TAK (yes) or NIE (no).

2
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..
2 2 2 2
xx
xx
.x
x.

TAK
NIE

Hint

Translated by ChatGPT 5