슈퍼맨은 지구에서 크립톤까지 이동하던 도중 웜 홀에 빠져버려 알 수 없는 장소로 이동해버렸습니다. 슈퍼맨은 지구에서 본 주기적 혜성이 있던 걸 기억하고, 순간이동 된 지점에서도 몇 개의 주기적 혜성을 볼 수 있습니다. 슈퍼맨은 혜성들을 이용해 방향을 잡으려고 합니다만 먼저 지금 보고 있는 혜성이 맞는 혜성인지 알아내야합니다.

슈퍼맨이 지금 보고 있는 혜성은 가우시안 하이퍼 혜성입니다. 이 가우시안 하이퍼 혜성의 주기는 pi가 2차원 평면 상의 점 (xi, yi)인 수열 (p1, p2, ..., pn), 으로 표현될 수 있습니다. 모든 점은 정수입니다. 이 혜성은 점 pi에서 점 pi+1로 이동합니다. 이 수열은 주기적이므로 점 pn에 방문한 후 p1을 방문합니다. (인덱스들은 mod n으로 표현될 수도 있습니다.) 가우시안 하이퍼 혜성의 주기는 pi ≠ pi+1, pn ≠ p1이란 특징을 가지고 있기도 합니다.

슈퍼맨이 웜홀을 넘어올 때 시간과 공간이 비틀어졌습니다. 공간이 비틀어졌다는 건 모든 점이 회전하거나, X,Y축이 양수에 비례해 조정되거나, 위치가 변경되거나의 셋 중 하나를 뜻합니다. 시간이 비틀어졌다는 건 기존의 점 p1이 더이상 p1이 아닐 지도 모른다는 의미입니다.

예를들어 삼각형 모양의 하이퍼 혜성 ((0,0),(1,0),(0,1))은 지구에선 ((40,40),(20,20),(60,20)) 혹은 ((20,20),(60,20),(40,40)) 처럼 보였을 수도 있다는 겁니다. 여기서 시간이나 공간을 뒤집혀지는 경우는 없습니다. 예를들어 위의 혜성은 지구에서 ((0,1),(1,0),(0,0)) 처럼 보였을 순 없다는 뜻입니다.

문제는 슈퍼맨이 지구에서 본 가우시안 하이퍼 혜성의 주기 수열과 지금 보고 있는 혜성의 주기가 주어졌을 때 과연 지금 보고 있는 혜성이 지구에서 본 혜성과 같은 혜성인지 출력하는 프로그램을 작성하세요

입력

• 각 테스트 케이스의 첫 번째 줄은 정수 이 n(1 ≤ n ≤ 500000)이 입력됩니다.
• 다음 n 줄에 공백으로 구분 된 xi, yi 쌍이 입력됩니다. 각 줄의 숫자는 지구에서 봤을 때의 점들의 주기입니다.
• 다음 n 줄에도 같은 형식으로 x'i, y'i 쌍이 입력됩니다. 각 줄의 숫자는 지금 슈퍼맨이 보고 있는 점들의 주기입니다.

입력

출력

입출력 예

입력

3
3
0 0
1 0
0 1
20 20
60 20
40 40
4
0 0
1 1
0 0
1 1
30 30
19 23
30 30
19 23
4
0 0
1 0
1 1
0 1
0 0
2 0
2 1
0 1

출력

3
1
0

※ 이 문제는 번역이 이상한 것도 있지만 원문도 만만치 않게 헷갈리게 쓰여 있습니다. 원문이 보고 싶으신 분은  cemc.uwaterloo.ca/contests/computing/2013/Stage2/day2.pdf에서 Problem 2를 읽어보세요.

출처:CEMC (CCC 2013 Stage 2)
번역:ladown21