题目描述

Berland 首都的一条主干道可以看作长度为 $s$ 的线段。道路上有 $n$ 个交通信号灯，第 $i$ 个信号灯由四个整数 $x_i,r_i,g_i,d_i$ 描述：

• $x_i$：信号灯距离道路起点的位置；
• $r_i$：红灯持续时间；
• $g_i$：绿灯持续时间；
• $d_i$：从时刻 $0$ 开始，第一个非负的“由绿灯切换为红灯”的时刻。

信号灯从很久以前就一直按周期 $r_i+g_i$ 工作。因此其绿灯区间周期性出现。车辆恰好在颜色切换的瞬间经过，不算闯红灯。

国王在时刻 $0$ 从道路起点出发，并始终以恒定速度 $v_0$ 行驶。交通部长可以把任意一些信号灯改成“永久绿灯”，从而保证国王一路不遇到红灯。

速度必须满足 $v_{min}\le v_0\le v_{max}$。请选择 $v_0$，使需要改成永久绿灯的信号灯数量最少；如果有多个速度都能达到最少数量，则选择其中最大的速度。

输入格式

第一行四个整数 $n,s,v_{min},v_{max}$，满足：

$1\le n<20000$，$1\le s\le20000$，$10\le v_{min}\le v_{max}\le50$。

接下来 $n$ 行，每行四个整数 $x_i,r_i,g_i,d_i$：

$1\le x_i\le s-1$，$10\le r_i,g_i\le20$，$0\le d_i<r_i+g_i$。

任意两个信号灯的位置不同。

输出格式

第一行输出最优速度 $v_0$，小数点后至少输出 $10$ 位数字。

第二行输出需要切换为永久绿灯的信号灯数量 $k$。

第三行输出这 $k$ 个信号灯的编号，编号按照输入顺序从 $1$ 开始，顺序任意。当 $k=0$ 时，第三行可以为空。

样例 1

样例输入

3 1000 10 30
500 10 10 10
501 10 10 0
600 10 10 0

样例输出

16.7000000000
0

样例 2

样例输入

2 1000 10 30
500 10 10 10
600 10 20 2

样例输出

25.0000000000
0

样例 3

样例输入

4 1000 10 30
800 10 15 20
500 20 10 15
501 20 10 5
600 10 20 15

样例输出

20.0400000000
1
2