불규칙한 케이크

Mary the Mathematician는 몇 년 전에 자신이 세운 제과점을 운영하고 있지만, 오랫동안 항상 똑같은 직사각형과 원형 케이크만 구워 온 탓에 지루해졌다. 다음 생일에는 x=0와 x=W 사이에 있는 두 "polylines" 사이의 영역으로 정의되는 불규칙한 케이크를 굽고 싶어 한다. 이 두 꺾은선을 각각 아래쪽 경계와 위쪽 경계라고 부른다.

형식적으로, 꺾은선은 왼쪽에서 오른쪽으로 이어지는 점들의 수열 ($P_{0}$, $P_{1}$, ..., $P_{n}$)로 정의된다. 연속한 점들을 연결하여 일련의 선분을 만들며, 이 선분들이 함께 꺾은선을 이룬다.

오늘은 Mary의 생일이며, Mary는 각각 L개의 점과 U개의 점으로 이루어진 두 꺾은선에 둘러싸인 불규칙한 케이크를 구웠다. "Happy Birthday,"를 부른 뒤, 그녀는 케이크를 넓이가 같은 G개의 조각으로 나누기 위해 G-1개의 수직 절단을 하려고 한다. 그러면 이 케이크 조각들을 모든 손님과 나눌 수 있다. 하지만 케이크의 불규칙한 모양 때문에 이 작업은 상당히 까다롭다. 어디를 잘라야 하는지 결정하도록 도와줄 수 있는가?

제한

1 ≤ T ≤ 100. 1 ≤ W ≤ 1000. 2 ≤ L ≤ 100. 2 ≤ U ≤ 100. 모든 좌표는 -1000 이상 1000 이하의 정수이다. 두 경계에서 가장 왼쪽에 있는 점의 x좌표는 0이다. 두 경계에서 가장 오른쪽에 있는 점의 x좌표는 W이다. 같은 경계에 속한 점들은 x좌표가 증가하는 순서로 정렬되어 있다. 같은 경계에 속한 점들의 x좌표는 서로 다르다. 0 이상 W 이하인 모든 x에서 아래쪽 경계는 항상 위쪽 경계보다 엄격히 아래에 있다. (즉, 모든 x 위치에서 아래쪽 경계의 y좌표는 위쪽 경계의 y좌표보다 작다.) 메모리 제한: 1GB.

소규모 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ G ≤ 3. 시간 제한: 30초.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ G ≤ 101. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 정수 W(케이크의 너비), L(아래쪽 경계에 있는 점의 수), U(위쪽 경계에 있는 점의 수), G(파티에 참석한 손님의 수)가 포함된 한 줄로 시작한다.

이어서 아래쪽 경계를 나타내는 L개의 줄이 주어진다. i번째 줄에는 아래쪽 경계의 i번째 점의 좌표를 나타내는 두 정수 $x_{i}$와 $y_{i}$가 주어진다. 그 뒤에는 위쪽 경계를 나타내는 U개의 줄이 더 주어진다. 여기서 j번째 줄에는 위쪽 경계의 j번째 점의 좌표를 나타내는 두 정수 $x_{j}$와 $y_{j}$가 주어진다.

각 테스트 케이스마다 G개의 줄을 출력한다. 첫 번째 줄에는 "Case #x:"을 출력해야 하며, 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 다음 G-1개의 줄에는 절단해야 하는 위치의 x좌표를 가장 왼쪽 절단부터 가장 오른쪽 절단까지 순서대로 출력해야 한다.

상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 간주한다.