Page not loading? Try clicking here.
Placeholder

#5499

화가 곰 (Stamp Grid) 1s 32MB

Problems

곰의 그림은 N \times N 도화지에 흑백 그림으로, 특정 칸은 칠해지고 특정 칸은 비어 있으며 N \times N 배열(1≤N≤20)로 표현할 수 있다.

도화지의 특정 칸에 칠해져 있으면 '*', 그렇지 않으면 '.' 으로 표현한다.

곰은 K \times K(1≤K≤N) 도장과 빈 N \times N 도화지 한 장을 가지고 있다.

곰은 도장을 시계 방향으로 90°씩 회전할 수 있으며 도장이 도화지 안에 완전히 들어있으면 그 영역에 도장을 찍을 수 있다.

정확하게는 i∈[1,N−K+1] 및 j∈[1,N−K+1]를 만족하는 정수 i,j를 선택하고 각 (i',j')에 대해 1≤i',j'≤K, 도화지에서 (i+i'−1,j+j'−1)은 도장의 (i',j')에 잉크가 있다면 검정색으로 칠해진다.

곰은 도장을 찍는 도중에 도장을 언제든 회전시킬 수 있으며 도화지에 한번 검정색으로 칠해지면 계속 검정색으로 남아있다.

곰은 자신의 도장으로 원하는 그림을 만드는 것이 가능한지 궁금하다.

각 T(1≤T≤100)개의 케이스에 대해 답을 출력하라.


Input

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다,

첫 줄에 N이 주어진다.

다음 N줄에 걸쳐 곰이 원하는 그림이 주어진다. 그림은 '*'과 '.'으로 이루어져 있다.

그 후 K가 주어진다.

다음 K줄에 걸쳐 곰이 가지고 있는 도장의 모양이 주어진다. 도장은 잉크가 있는 '*'과 잉크가 없는 '.'으로 이루어져 있다.

각 테스트 케이스는 빈 줄로 구분되어 주어진다.


Output

각 테스트 케이스마다 "YES" 또는 "NO"를 출력한다.


Example 

4



2

**

*.

1

*



3

.**

.**

***

2

.*

**



3

...

.*.

...

3

.*.

...

...



3

**.

.**

..*

2

.*

*.
YES

YES

NO

YES

첫 번째 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

(1,1)에 도장 찍기

(1,2)에 도장 찍기

(2,1)에 도장 찍기

두 번째 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

(2,2)에 도장 찍기

(2,1)에 도장 찍기

90도 도장 회전

90도 도장 회전

(1,2)에 도장 찍기

세 번째 테스트 케이스는 가운데에 색칠 할 수 없다.

네 번재 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

90도 도장 회전

(1,1)에 도장 찍기

(1,2)에 도장 찍기

(2,2)에 도장 찍기


Source

USACO 2023 February Bronze

You must sign in to write code.