컬링

2022은 Winter Olympics의 해이다! 컬링은 기술과 전략, 때로는 약간의 운이 필요하기 때문에 가장 인기 있는 동계 스포츠 중 하나이다.

컬링 경기에서는 두 팀이 긴 빙판 위에서 무거운 화강암 스톤을 미끄러뜨리며 경쟁한다. 스톤은 보통 손잡이의 빨간색과 노란색으로 구분되므로, 두 팀을 빨간 팀과 노란 팀이라고 부른다. 컬링 경기는 여러 엔드(하위 경기)로 구성된다. 각 엔드에서 $8$개의 스톤을 보유한 각 팀은 번갈아 가며 스톤을 긴 빙판 너머 하우스라고 하는 원형 표적 구역을 향해 미끄러뜨린다. 스톤은 기존 스톤과 충돌하여 자신의 진행 방향과 다른 스톤의 위치를 바꿀 수 있다(경기 구역 밖으로 밀어내는 것도 포함한다). 대략적으로 말하면, 각 팀의 목표는 자신의 스톤을 가능한 한 하우스의 중심에 가깝게 놓는 것이다.

기하학적으로 하우스와 스톤은 각각 원과 원판(원으로 둘러싸인 영역)으로 모델링할 수 있으며, 각 엔드가 끝났을 때의 득점 규칙은 다음과 같이 엄밀하게 요약된다.

• 각 스톤은 $2$-차원 평면 위에 있는 반지름 $\mathbf{R_s}$의 원판으로 볼 수 있다.

• 하우스는 $(0, 0)$을 중심으로 하는 반지름 $\mathbf{R_h}$의 원이다.

• 하우스 안에 있는 스톤만 득점에 고려한다. 스톤의 일부라도 하우스를 나타내는 원 위나 그 내부에 있으면 그 스톤은 하우스 안에 있다. 접하는 경우도 포함한다.

• 하우스 안에 있는 자기 팀의 각 스톤에 대해, 그 스톤보다 중심에 더 가까운(유클리드 거리 기준) 상대 팀의 스톤이 없다면 팀은 $1$점을 얻는다. 이 문제에서는 중심 $(0,0)$까지의 거리가 같은 두 스톤은 없다고 가정한다.

두 팀이 경기를 진행하여 방금 모든 스톤을 투구했다. 컬링 시트 위에 남아 있는 빨간 팀의 스톤은 $\mathbf{N}$개이며 중심은 각각 $(\mathbf{X_1}, \mathbf{Y_1}), (\mathbf{X_2}, \mathbf{Y_2}), \dots, (\mathbf{X_N}, \mathbf{Y_N})$이고, 노란 팀의 남은 스톤은 $\mathbf{M}$개이며 중심은 각각 $(\mathbf{Z_1}, \mathbf{W_1}), (\mathbf{Z_2}, \mathbf{W_2}), \dots, (\mathbf{Z_M}, \mathbf{W_M})$이다. 이제 두 팀의 점수를 구해야 한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{R_s} \lt \mathbf{R_h} \le 10^4$. $0 \le \mathbf{N} \le 8$. 모든 $i$에 대해 $-2 \times 10^4 \le \mathbf{X_i} \le 2 \times 10^4$. 모든 $i$에 대해 $-2 \times 10^4 \le \mathbf{Y_i} \le 2 \times 10^4$. 모든 $i$에 대해 $-2 \times 10^4 \le \mathbf{Z_i} \le 2 \times 10^4$. 모든 $i$에 대해 $-2 \times 10^4 \le \mathbf{W_i} \le 2 \times 10^4$. 각 스톤의 중심과 하우스의 중심 $(0, 0)$ 사이의 거리는 서로 다르다. 즉, 하우스의 중심까지의 거리가 같은 두 스톤은 없다. 어떤 두 스톤도 겹치지 않는다(단, 두 스톤이 접할 수는 있다).

테스트 세트 1

$\mathbf{M} = 0$.

테스트 세트 2

$0 \le \mathbf{M} \le 8$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 공백으로 구분된 두 정수 $\mathbf{R_s}$와 $\mathbf{R_h}$가 포함된 한 줄로 시작한다.

다음 줄에는 정수 $\mathbf{N}$가 주어진다. 이어지는 $\mathbf{N}$개 줄 중 $i$-번째 줄에는 공백으로 구분된 두 정수 $\mathbf{X_i}$와 $\mathbf{Y_i}$가 주어진다.

그 후에도 마찬가지로, 다음 줄에는 정수 $\mathbf{M}$가 주어진다. 이어지는 $\mathbf{M}$개 줄 중 $i$-번째 줄에는 공백으로 구분된 두 정수 $\mathbf{Z_i}$와 $\mathbf{W_i}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$ $z$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 빨간 팀의 점수이며, $z$는 노란 팀의 점수이다.

다음 그림은 예제 케이스 #1을 보여 준다. 내부가 연한 파란색인 큰 원은 하우스를 나타내고, 빨간 원판은 빨간 팀의 스톤을 나타낸다.

이 경우 노란 팀은 하우스 안에 남은 스톤이 없으므로, 빨간 팀은 하우스 안에 있는 자기 팀의 각 스톤마다 한 점을 얻는다. 중심이 $(6, 1)$인 스톤을 제외한 기존의 모든 스톤이 하우스 안에 있다(그 스톤의 중심이 $(6, 0)$였다면 하우스의 경계에 닿았을 것이다). 따라서 빨간 팀은 $3$점을 얻는다.

추가 예제 - 테스트 세트 2

다음 그림은 예제 케이스 #1을 보여 준다. 큰 원과 빨간 원판들에 더해, 노란 원판은 노란 팀에 남은 유일한 스톤을 나타낸다.

이 경우 두 팀 모두 하우스 안에 스톤이 있다. $(1, 0)$에 있는 빨간 스톤은 하우스 안에 있고, 그 스톤보다 하우스의 중심에 더 가까운 노란 스톤이 없으므로 한 점을 얻을 수 있다. 다른 빨간 스톤(중심이 $(-3, 0)$인 스톤)도 하우스 안에 있지만, 중심이 $(0, 2)$인 노란 스톤이 그 스톤보다 중심 $(0,0)$에 더 가깝기 때문에 점수를 얻을 수 없다. 또한 $(1, 0)$에 있는 빨간 스톤이 존재하므로 노란 스톤도 점수를 얻을 수 없다. 따라서 빨간 팀은 $1$점을 얻고 노란 팀은 $0$점을 얻는다.