프랙탈

프랙탈은 흥미로운 수학적 대상으로, 다음과 같은 성질을 자주 가진다.

• 임의로 작은 규모에서도 나타나는 세밀한 구조,
• 자기 유사성: 확대하면 부분이 전체의 복사본처럼 보인다,
• 간단한 재귀적 정의.

근사적인 프랙탈은 구름, 눈송이, 산맥, 강줄기 등 자연 곳곳에서 볼 수 있다.

이 문제에서는 다음 절차로 만들어지는 프랙탈을 생각한다. 먼저 점 $p_1, p_2, \dots, p_n$ 으로 정의되는 꺾은선(연결된 선분들의 사슬)에서 시작한다. 이 꺾은선이 깊이 1 의 프랙탈이다.

깊이 2 의 프랙탈을 만들려면 각 선분을 원래 꺾은선 전체를 축소·회전한 복사본으로 바꾼다. 이 복사본은 꺾은선의 첫 점 $p_1$ 을 선분의 시작점으로, 마지막 점 $p_n$ 을 선분의 끝점으로 보내는 유일한 닮음 변환(회전과 균등 축소만 사용하며 반사는 없다)으로 얻는다. 이 치환을 반복하여 매 단계마다 현재의 모든 선분을 원래 꺾은선의 변환된 복사본으로 바꾸면, 점점 더 세밀한 구조를 가지는 임의의 깊이 $d$ 의 프랙탈을 얻는다.

이러한 프랙탈의 복잡도는 깊이가 커질수록 빠르게 증가한다. 전체 길이에 대한 비율 $f$ 가 주어질 때, $p_1$ 에서 출발하여 프랙탈 곡선을 따라 그 비율만큼 이동한 뒤 도달하는 점의 좌표를 구하려고 한다.

첫 줄에는 테스트 케이스의 수를 나타내는 정수 $c$ ($1 \le c \le 200$) 가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 꺾은선의 점 개수를 나타내는 정수 $n$ ($3 \le n \le 100$) 이 한 줄에 주어진다,
• 이어지는 $n$ 개의 줄 중 $i$ 번째 줄에는 꺾은선의 연속된 점을 나타내는 두 정수 $x_i$ 와 $y_i$ ($-1000 \le x_i, y_i \le 1000$) 가 주어진다,
• 프랙탈의 깊이를 나타내는 정수 $d$ ($1 \le d \le 10$) 가 한 줄에 주어진다,
• 이동하는 전체 길이의 비율을 나타내는 실수 $f$ ($0 \le f \le 1$) 가 한 줄에 주어진다.

꺾은선의 각 선분의 길이는 첫 점 $(x_1, y_1)$ 과 마지막 점 $(x_n, y_n)$ 사이의 거리보다 엄밀히 작다. 꺾은선 전체의 길이는 이 거리의 두 배보다 엄밀히 작다.

각 테스트 케이스마다, 프랙탈 길이의 비율 $f$ 만큼 이동한 뒤 도달하는 점의 좌표를 한 줄에 출력한다.

$(x,y)$ 형식으로 출력하되, $x$ 와 $y$ 는 각각 소수점 아래 정확히 여섯 자리 로 쓰고 공백은 넣지 않는다. 예: (0.426777,2.000000).