分形是非常酷的数学对象。它们有很多有趣的性质，通常包括：

• 在任意小的尺度上都具有精细的结构；
• 自相似性，即放大后看起来像它自身的一个副本；
• 一个简单的、递归的定义。

自然界中存在许多近似的分形，例如云朵、雪花、山脉和河流网络等结构。

在本题中，我们考虑由以下算法生成的分形：我们从一条折线（即一组连接的线段）开始。这就是我们所说的深度为 1 的分形（见最左边的图）。为了获得深度为 2 的分形，我们将每条线段替换为原始折线的缩放和旋转版本（见中间的图）。通过重复地用折线替换线段，我们可以获得任意深度的分形，从而产生非常精细的结构。最右边的图显示了深度为 3 的分形。

随着深度的增加，近似分形的复杂度会迅速增加。我们想要知道在遍历了其总长度的特定比例后，我们最终会到达哪个位置。

输入格式

输入开头第一行包含一个整数 $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)$ 之间的距离。整条折线的总长度小于该距离的两倍。

输出格式

对于每个测试用例，输出一行，包含我们最终到达的坐标。格式为 (x,y)，其中 $x$ 和 $y$ 为两个浮点数。两个坐标的绝对误差均应小于 $10^{-6}$。

样例

输入样例 1

1
4
-2 -2
0 0
0 2
2 2
3
0.75

输出样例 1

(0.4267766953,2)