400359: GYM100151 G Traffic Lights

The main street of Berland's capital is a segment with length s. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers x_i, r_i, g_i, d_i, which stand for:

• x_i — the distance from the beginning of the street to the traffic light (1 ≤ x_i ≤ s - 1),
• r_i — the duration of the red light illumination (10 ≤ r_i ≤ 20),
• g_i — the duration of the green light illumination (10 ≤ g_i ≤ 20),
• d_i — the minimum non-negative moment of time when the traffic light changes the light from green to red (0 ≤ d_i < r_i + g_i).

Each traffic light retains its light cycle from the ancient past.

The King of Berland asked the transport minister to customize the traffic lights according to a "green wave" principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.

Now it is time to show the "green wave’’ to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time 0 from the beginning of the street. So the minister decided to choose some speed v₀ and tell the king that the "green wave" works specifically for this speed. Moreover, they can switch any number of traffic lights to the "always green" mode. The minister' aim is to ensure that if the King drives through the street at the recommended speed v₀ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.

Any transport's maximum speed is limited in Berland: it should not exceed v_max. On the other hand, the King will be angry if the recommended speed is less than v_min. Thus, the minister should choose such value of v₀, which satisfies the inequation v_min ≤ v₀ ≤ v_max.

Help the minister to find such v₀ value, that the number of traffic lights to switch to the "always green" mode is minimum. If v₀ is not uniquely defined, choose the maximum possible value of v₀.

The first line of the input data contains four integers n, s, v_min and v_max (1 ≤ n < 20000, 1 ≤ s ≤ 20000, 10 ≤ v_min ≤ v_max ≤ 50), where n is the number of traffic lights on the street, s is the length of the street in meters, v_min and v_max are speed limits in meters per second.

Then n lines contain descriptions of the traffic lights, one per line. Each description consists of four integer numbers x_i, r_i, g_i, d_i (1 ≤ x_i ≤ s - 1, 10 ≤ r_i, g_i ≤ 20, 0 ≤ d_i < r_i + g_i), where x_i, r_i, g_i, d_i are explained above. Values r_i, g_i, d_i are given in seconds and x_i — in meters. No two traffic lights are located at one point.

On the first line, print the sought value v₀ containing no less than 10 digits after the decimal point. On the second line, print the number of traffic lights that need to be switched to the "always green" mode for the found v₀. The third line should contain the numbers of those traffic lights. It doesn't matter you print empty third line or print only two lines in case of no traffic lights to switch. The traffic lights are numbered starting from 1 in the order in which they appear in the input data. Print the numbers of the traffic lights in any order.

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

16.7000000000
0

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

25.0000000000
0

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

20.0400000000
1
2