Fractal

Fractals are fascinating mathematical objects. They often share several interesting properties:

• fine structure at arbitrarily small scales;
• self-similarity: when magnified, a part looks like a copy of the whole;
• a simple, recursive definition.

Approximate fractals appear throughout nature, for example in clouds, snowflakes, mountain ranges, and river networks.

In this problem we consider fractals generated by the following procedure. We start with a polyline, that is, a chain of connected line segments defined by points $p_1, p_2, \dots, p_n$. This polyline is the fractal of depth one.

To build the fractal of depth two, we replace every line segment by a scaled and rotated copy of the whole original polyline: the copy is the unique similarity transform (rotation and uniform scaling only, no reflection) that maps the polyline's first point $p_1$ onto the segment's start and its last point $p_n$ onto the segment's end. Repeating this replacement, at each step substituting every current segment by a transformed copy of the original polyline, yields fractals of arbitrary depth $d$ with increasingly fine structure.

The complexity of such a fractal grows rapidly with its depth. Given a fraction $f$ of the total length, we want to know the coordinate of the point reached after travelling that fraction along the fractal curve, starting from $p_1$.

The first line contains a single integer $c$ ($1 \le c \le 200$), the number of test cases. Each test case is given as follows:

• one line with an integer $n$ ($3 \le n \le 100$), the number of points of the polyline;
• $n$ lines, the $i$-th of which contains two integers $x_i$ and $y_i$ ($-1000 \le x_i, y_i \le 1000$), the consecutive points of the polyline;
• one line with an integer $d$ ($1 \le d \le 10$), the depth of the fractal;
• one line with a floating point number $f$ ($0 \le f \le 1$), the fraction of the total length that is traversed.

The length of each line segment of the polyline is strictly smaller than the distance between the first point $(x_1, y_1)$ and the last point $(x_n, y_n)$. The total length of the polyline is strictly smaller than twice that distance.

For each test case, print one line with the coordinate of the point reached after traversing the fraction $f$ of the fractal's length.

Print it in the form $(x,y)$ where $x$ and $y$ are each written with exactly six digits after the decimal point and with no spaces, for example (0.426777,2.000000).