종이접기

NYPC 2018 · 예선

크기가 N×MN \times M 인 종이를 계속 접어 크기가 1×11 \times 1 이 될 때까지 접은 후 이를 펼치면 종이엔 줄무늬가 생긴다. 어떤 줄무늬는 위로 볼록하고, 어떤 것은 아래로 볼록한 모양을 띄게 된다. 위로 볼록한 무늬를 굵은 실선으로, 아래로 볼록한 무늬를 굵은 점선으로 나타내자. 아래 그림은 2×32 \times 3 크기의 종이를 어떤 순서로 접었나에 따른 서로 다른 줄 무늬를 보여주고 있다.

격자의 정보를 나타내는 자연수 NNMM, 그리고 줄무늬를 나타내는 정보가 주어질 때, 그런 무늬가 실제로 종이를 접은 후 펼쳐서 얻어진 그림인지, 아니면 인위적으로 그린 그림인지를 판단하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 수 TT (1T101 \le T \le 10)가 주어진다.

각 테스트 케이스의 첫째줄엔 종이의 세로 크기를 나타내는 정수 NN(2N502 \le N \le 50)과 가로 크기를 나타내는 정수 MM(2M502 \le M \le 50)이 주어진다.

이어지는 NN줄 각각엔 M1M-1 개의 정수(00 또는 11)가 주어지는데 이는 격자의 세로방향 무늬에 대한 정보이다. 즉, ii 번째 줄에 있는 M1M-1개 정수는 격자의 ii 번째 행에 있는 M1M-1개의 세로 방향에 관한 무늬 정보이다. 11은 위로 볼록한 무늬를, 00은 아래로 볼록한 무늬를 의미한다.

이어지는 N1N-1 줄 각각엔 MM 개의 정수(00 또는 11)가 주어지는데 이는 가로방향 무늬에 대한 정보이다. 즉, ii 번째 줄에 있는 MM 개 정수는 격자의 ii 번째 행에 있는 MM 개의 가로 방향에 관한 무늬 정보이다. (아래 그림 참조)

출력 형식

한 줄로 결과를 출력한다. 주어진 무늬 정보가 실제로 종이를 접은 후 펼쳐서 얻어지는 것이면 11, 그렇지 않으면 00을 출력한다.

예제 1

입력

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

출력

1 1

예제 2

입력

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

출력

1 0

예제 3

입력

1 2 4 0 1 1 1 1 0 1 1 1 0

출력

0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 20

N=M=2N = M = 2 이다.

종류 2: 55

세로무늬 값은 모두 11이다.(즉, 세로선은 모두 위로 볼록하다.)

종류 3: 125

별다른 제약조건 없음.

해설