Cambeet 居住在一个平面上。他想从位于 $(x_h, y_h)$ 的家前往位于 $(x_e, y_e)$ 的展览馆。在这个平面上有两种旅行方式，每种方式都会消耗能量。

第一种方式是沿两点之间的线段移动。此类旅行所需的能量等于线段的长度：从点 $(x_a, y_a)$ 移动到点 $(x_b, y_b)$ 消耗 $\sqrt{|x_b - x_a|^2 + |y_b - y_a|^2}$ 单位能量。

第二种方式是使用平面上的 $n$ 个“交通十字”（transport pluses），编号为 $1$ 到 $n$。第 $i$ 个十字的中心位于 $(x_i, y_i)$，它连接所有满足 $x = x_i$ 或 $y = y_i$ 的点：人们可以在任何此类点之间瞬间移动，只需在移动应用中输入坐标即可。每次使用任意一个十字都会消耗 $t$ 单位能量。

Cambeet 可以按任意顺序使用这些旅行方式。请帮助他找到一条总能量消耗最小的路径。

输入格式

第一行包含两个整数 $n$ 和 $t$：交通十字的数量以及每次使用十字消耗的能量 ($0 \le n, t \le 100$)。 第二行包含两个整数 $x_h$ 和 $y_h$：Cambeet 家的坐标 ($0 \le x_h, y_h \le 100$)。 第三行包含两个整数 $x_e$ 和 $y_e$：展览馆的坐标 ($0 \le x_e, y_e \le 100$)。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$：第 $i$ 个十字中心的坐标 ($0 \le x_i, y_i \le 100$)。

所有输入数据均为整数。然而，Cambeet 可以自由前往坐标为任意实数的点。

输出格式

第一行输出一个实数：总消耗能量。 第二行输出一个整数 $k$：路径中的移动次数 ($0 \le k \le 10\,000$)。 接下来的 $k$ 行，每行输出三个值 $p_j, x_j, y_j$：所使用的十字编号以及下一个目标的坐标。$p_j$ 的值为 $0$ 表示沿线段移动，$p_j$ 为 $1$ 到 $n$ 之间的整数表示使用对应编号的十字。坐标可以是 $0$ 到 $100$ 之间的任意实数。使用十字时，该十字必须连接当前位置和下一个目标。路径必须以 $(x_e, y_e)$ 结束。

你可以输出任何总能量消耗最小的路径。如果总消耗能量与最小可能值的差不超过 $10^{-3}$，则答案被视为正确。

样例

输入格式 1

1 2
1 1
5 3
6 2

输出格式 1

4.000000
4
0 1 1.67
0 1 2
1 5 2
0 5 3

说明

输入格式 2

2 1
1 1
6 1
1 3
6 3

输出格式 2

2.0
2
1 5 3
2 6 1

说明