Problem J: 모눈종이 퍼즐

Problem J: 모눈종이 퍼즐

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 60  Solved: 20
[Submit] [Status] [Web Board] [Creator:]

Description

모양과 크기가 다른 두 직사각형 모양의 반투명 모눈종이가 있다. 몇 개의 칸을 이미 누군가가 낙서를 한다고 색칠을 해둔 모양이다.

이것을 이리 저리 돌려보며 가지고 놀던 mQueue는 두 모눈종이를 왼쪽 상단 모서리 부분(0,0)을 기준으로 4방향으로 돌려보며 겹쳤을 때 나올 법한 결과를 예측해보기로 하였다.

이 예측 결과가 맞는지 확인해 줄 수 있는 프로그램를 작성해 주자.

예를 들면 아래와 같이 4*3 모눈종이와 6*5 모눈종이가 있다.


앞의 모눈종이를 한번 회전하여 겹칠 경우 위의 모양은 만들어 낼 수 있지만 아래의 문양은 만들어 낼 수 없다.(뒤에 나온 큰 모눈종이는 회전하지 않는다)



Input

첫 줄에 테스트케이스 T가 입력된다.

그 다음 줄부터 첫번째 모눈종이의 크기 M1,  N1이 입력된 후 M1 x N1 크기의 모눈종이 값이 입력된다. 그런 다음  두 번째 모눈종이의 크기 M2, N2와 M2 x N2 크기의 모눈종이 값이 입력된 후에 mQueue가 예측한 모눈이 차례로 입력된다. 이러한 입력이 테스트케이스 수 만큼 입력된다.

(0 < T <1,000 ,   2 < M1, N1 < M2, N2 < 100)

Output

M1*N1 모눈종이를 0도, 90도, 180도, 270도로 4번 회전하여 M2*N2의 (0,0)을 기준으로 붙였을 때, 그 결과들 중 하나라도 주어진 결과가 나올 수 있는지를 서식에 맞게 한 줄씩 출력한다.

출력 예시에서 \0/, \1/ 등의 숫자는 테스트케이스의 순번을 나타낸다.(자세한 출력 형식은 출력 예시를 참고하시오.)

Sample Input Copy

2
3 4
0 1 0
0 0 1
1 1 0
0 1 0
6 5
1 0 0 1 0 0
0 0 1 1 1 1
0 0 0 0 0 0
1 1 0 1 1 0
0 1 0 0 0 1
1 1 0 1 0 0
1 1 1 1 1 1
0 0 1 0 0 0
1 1 0 1 1 0
0 1 0 0 0 1
3 4
0 1 0
0 0 1
1 1 0
0 1 0
6 5
1 0 0 1 0 0
0 0 1 1 1 1
0 0 0 0 0 0
1 1 0 1 1 0
0 1 0 0 0 1
1 1 0 1 0 0
1 1 1 1 1 1
0 0 1 1 0 0
1 1 0 1 1 0
0 1 0 0 0 1

Sample Output Copy

\0/ : True
\1/ : False

HINT

2차원 배열 연습문제입니다.