Background

Special for beginners, ^_^

Description

给出一系列点p_1, p_2, ... , p_n，将其分成不多余m个连续的段，第i段内求一个点q_i，使得q_i到这段内点的距离的最大值的最大值最小

Format

Input

第一行，n m 下面n行，每行两个整数，表示p_i的x y坐标 1<=m<=n<=100000 坐标范围[-1000000,1000000] 0<p,q,r<=150，输入中至少包含一个’N’

Output

第一行，q_i到这段内点的距离的最大值的最大值的最小值 第二行，分成的段数k 下面k行，每行两个实数，表示q_k的x y坐标

All the real numbers should be printed with at most 15 digits after the decimal point.

Samples

7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2

3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199

Limitation

1s, 1024KiB for each test case.