불규칙한 케이크 (큰 입력)

수학자 메리는 몇 년 전에 빵집을 열었다. 그동안 직사각형 케이크와 원형 케이크만 계속 구워 온 것이 지겨워져서, 다음 생일에는 불규칙한 케이크를 굽기로 했다. 불규칙한 케이크란 $x=0$부터 $x=W$까지 뻗은 두 꺾인선 사이의 영역이다. 아래쪽 꺾인선을 아래 경계, 위쪽 꺾인선을 위 경계라고 부른다.

꺾인선은 왼쪽에서 오른쪽으로 나열한 점의 열 $(P_0, P_1, \ldots, P_n)$으로 정의한다. 이웃한 두 점을 선분으로 이어 붙이면 하나의 꺾인선이 된다.

오늘은 메리의 생일이다. 메리는 점이 $L$개인 아래 경계와 점이 $U$개인 위 경계로 둘러싸인 불규칙한 케이크를 구웠다. 생일 축하 노래를 부른 뒤, 메리는 케이크를 수직으로 $G-1$번 잘라서 넓이가 똑같은 $G$조각으로 나누려고 한다. 그러면 손님 모두에게 한 조각씩 나눠 줄 수 있다. 그런데 케이크 모양이 불규칙해서 자를 위치를 정하는 일이 만만치 않다. 메리가 어디를 잘라야 하는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 네 개 $W$, $L$, $U$, $G$가 공백으로 구분되어 주어진다. $W$는 케이크의 너비, $L$은 아래 경계의 점 개수, $U$는 위 경계의 점 개수, $G$는 파티에 온 손님 수다.

다음 $L$개의 줄에는 아래 경계가 주어진다. 그중 $i$번째 줄에는 아래 경계의 $i$번째 점의 좌표 $x_i$와 $y_i$가 주어진다. 그다음 $U$개의 줄에는 위 경계가 같은 형식으로 주어진다.

제한

• $1 \le T \le 100$
• $1 \le W \le 1000$
• $2 \le L \le 100$
• $2 \le U \le 100$
• $2 \le G \le 101$
• 모든 좌표는 $-1000$ 이상 $1000$ 이하의 정수다.
• 두 경계 모두 가장 왼쪽 점의 $x$좌표는 $0$이고, 가장 오른쪽 점의 $x$좌표는 $W$다.
• 같은 경계에 속한 점은 $x$좌표가 증가하는 순서로 주어지고, $x$좌표가 서로 다르다.
• $0 \le x \le W$인 모든 $x$에서 아래 경계의 $y$좌표는 위 경계의 $y$좌표보다 작다.

각 테스트 케이스마다 $G$개의 줄을 출력한다. 첫째 줄에는 Case #x:를 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호다. 이어지는 $G-1$개의 줄에는 자를 위치의 $x$좌표를 왼쪽부터 순서대로 한 줄에 하나씩 출력한다.

케이크의 높이는 $0 \le x \le W$ 구간 전체에서 양수이므로 왼쪽부터 누적한 넓이는 $x$에 대해 엄격하게 증가한다. 따라서 자를 위치는 하나로 정해진다.

좌표는 소수점 아래 여섯째 자리까지 사사오입으로 반올림하고, 여섯 자리를 모두 채워서 출력한다. 정확한 값이 $5$이면 5.000000을 출력한다.