P3585 [POI 2015 R1] Seal

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.

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.

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

Translated by ChatGPT 5