一款流行的建筑 CAD 软件中有一个用于创建实体的操作，称为“Blend”。该操作接受位于两个平行平面上的两个轮廓，并在它们之间构建一个实体。每个轮廓在其平面内包围的区域成为实体的顶面或底面，并在两个轮廓之间构建一组侧面。

侧表面按以下方式构建（参见说明中的图 1）。在每个轮廓上选择一个起点。每个轮廓都有一个预定义的走向，即遍历方向。选择的起点由一条活动线段（一条直放线段）连接。接着，活动线段的端点沿轮廓移动：底面轮廓上的端点沿底面轮廓移动，顶面轮廓上的端点沿顶面轮廓移动。随着活动线段的移动，它扫过侧表面。为了获得所得实体的完整侧表面，每个端点必须绕相应的轮廓完整移动一圈。禁止将活动线段的端点逆着选定的轮廓遍历方向移动。

为了解决本题，假设每个轮廓都是由线段组成的闭合折线。请注意，上述规则具有歧义：通过改变活动线段两端移动的速度，你可以为轮廓构建各种各样的侧表面。为了消除歧义，引入了额外的规则。当活动线段的一个端点位于折线的顶点时，另一个端点也必须位于另一条折线的顶点。活动线段的这些位置定义了所创建实体的侧棱，而相邻侧棱之间的侧表面部分称为侧面。

因此，实体的每个侧面必须要么将其中一条折线的一条线段与另一条折线的一个顶点连接（三角形），要么将其中一条折线的一条线段与另一条折线的一条线段连接（四边形）。该四边形甚至可以是曲面的：在这种情况下，其精确的几何形状取决于活动线段两端点的相对移动速度。在现实中，这些速度也是受调控的，但这与本题无关。最终，如果我们选择构建哪些侧棱，即如何匹配给定折线的顶点，则所得实体将被严格定义。

通常，这由工程师（CAD 软件用户）来定义。为了简化，程序提供了一种默认匹配。它的选择方式是使所有侧棱的总长度尽可能小。编写一个程序，根据输入的轮廓计算该默认匹配。

请注意，此描述未提及侧表面的自交问题。当然，如果确实发生这些问题，严格来说该实体将不是一个实体。在使用“Blend”操作时，此类异常是可能且允许发生的，包括默认选择侧棱的情况。这些问题的发现和修正由完全不同的算法完成。

输入格式

第一行包含三个整数：$M$ —— 底面折线的顶点数，$N$ —— 顶面折线的顶点数，以及 $H$ —— 实体的绝对高度（$3 \le M, N \le 300$，$1 \le H \le 10^6$）。

接下来的 $M$ 行定义底面折线顶点的坐标。每行包含两个整数：$x$ 和 $y$ 坐标。顶点按照选定的折线遍历方向列出；最后定义的顶点之后是第一个定义的顶点。

剩余的 $N$ 行以相同的格式包含顶面折线的顶点坐标。

所有坐标的绝对值均不超过 $10^6$。底面折线位于平面 $z = 0$ 上，顶面折线位于平面 $z = H$ 上。每条折线上的所有顶点都是互不相同的。允许自交。

输出格式

在输出的第一行中，打印一个实数 $A$ —— 你的方案中侧棱的总长度，以及一个整数 $K$ —— 侧棱的数量（$\max(M, N) \le K \le M + N$）。

在接下来的 $K$ 行中，按照活动线段扫过的顺序打印侧棱。你可以从任意一条侧棱开始。对于每条侧棱，单独打印一行，包含两个整数 $i$ 和 $j$ —— 分别表示该侧棱连接的底面和顶面折线的顶点编号（$1 \le i \le M$，$1 \le j \le N$）。

数值 $A$ 与最优值之间的绝对或相对误差不能超过 $10^{-9}$。

样例

输入 1

3 3 1
0 0
2 0
1 1
3 -1
1 2
-1 -1

输出 1

4.878315177510850 3
1 3
2 1
3 2

输入 2

9 3 3
0 2
1 0
2 0
7 0
8 1
8 5
3 7
2 7
0 6
6 2
2 6
2 2

输出 2

33.210944197060996 9
1 3
2 3
3 3
4 1
5 1
6 1
7 2
8 2
9 2

说明

图 1：活动线段扫过的侧表面。

图 2：第二个样例：侧棱与侧面。