볼록 다각형의 덧셈

Convexman 씨는 볼록 다각형을 매우 좋아한다. 볼록 다각형을 연구하던 그는 다음과 같은 우아한 볼록 다각형 덧셈을 생각해냈다.

xy 평면 위의 두 점 $(x_1, y_1)$과 $(x_2, y_2)$의 합은 $(x_1 + x_2, y_1 + y_2)$이다. 다각형은 경계와 내부에 있는 모든 점의 집합으로 본다. 두 다각형 $S_1$과 $S_2$의 합 $S_1 + S_2$는 $v_1 \in S_1$, $v_2 \in S_2$를 만족하는 모든 점 $v_1 + v_2$의 집합이다. 두 볼록 다각형의 합은 항상 볼록 다각형이다. 음이 아닌 정수 $k$와 다각형 $S$에 대해 $0S = \{(0, 0)\}$이고, 양의 정수 $k$에 대해 $kS = (k - 1)S + S$이다. 이 문제에서는 선분과 점도 볼록 다각형으로 본다.

Convexman 씨는 두 볼록 다각형 $P$와 $Q$를 바탕으로 덧셈의 성질을 연구하며 많은 볼록 다각형을 만들었다. 그런데 어느 날 $P$와 $Q$의 꼭짓점 위치와 계산 과정을 적어 둔 종이를 실수로 버렸다. 남은 것은 $P$와 $Q$의 음이 아닌 정수 계수 선형 결합으로 표현된 볼록 다각형 $R$과 $S$의 꼭짓점 위치뿐이다.

$R = aP + bQ$,

$S = cP + dQ$.

다행히 그는 $P$와 $Q$의 모든 꼭짓점 좌표가 정수이고, 계수 $a$, $b$, $c$, $d$가 $ad - bc = 1$을 만족한다는 것을 기억한다.

그는 당신에게 주어진 볼록 다각형 $R$과 $S$로부터 $P$와 $Q$를 복원하는 프로그램을 부탁했다. 즉 $ad - bc = 1$을 만족하는 음이 아닌 정수 $a$, $b$, $c$, $d$와, 위 식을 만족하는 정수 좌표 꼭짓점을 가진 볼록 다각형 $P$와 $Q$를 구하라. 해는 여러 개일 수 있다. $P$와 $Q$ 넓이 합의 최솟값을 계산하라.

입력은 최대 40개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식으로 주어진다.

n m
x1 y1
...
xn yn
x'1 y'1
...
x'm y'm

$n$은 $R$의 꼭짓점 개수이고, $m$은 $S$의 꼭짓점 개수이다. 두 값은 $3 \le n \le 1000$, $3 \le m \le 1000$을 만족하는 정수이다. $(x_i, y_i)$는 $R$의 $i$번째 꼭짓점이고, $(x'_i, y'_i)$는 $S$의 $i$번째 꼭짓점이다. 모든 좌표는 $-10^6$ 이상 $10^6$ 이하의 정수이다. 각 다각형의 꼭짓점은 반시계 방향 순서로 주어진다. 한 다각형의 서로 다른 세 꼭짓점은 한 직선 위에 있지 않다.

입력의 끝은 0 0 한 줄로 표시된다.

각 데이터셋에 대해 $P$와 $Q$ 넓이 합의 두 배인 정수를 한 줄에 출력한다. $P$와 $Q$의 꼭짓점 좌표가 모두 정수이므로 넓이의 두 배는 항상 정수이다.