问题描述

数轴上有 $n$ 条线段，选 $m$ 条线段，使得他们的交集最大。

输入 / 输出格式

输入：第一行两个整数 $n,m$

第 $2$ 行至第 $n+1$ 行，每行两个正整数 $l,r$，表示每条线段的端点坐标。

输出：

第一行：一个正整数，表示交集长度。

第二行：最大交集的选择方法。

数据范围

$1 \le m \le n \le 10^6$，$1 \le$ 每条线段的端点坐标 $\le 10^9$

样例

输入

6 3
3 8
4 12
2 6
1 10
5 9
11 12

输出

4
1 2 4