540. Traffic Lights
Time limit per test: 1
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
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} ≤ s1),
 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 nonnegative 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_{0} 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_{0} 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_{0}, which satisfies the inequation
v_{min} ≤
v_{0} ≤
v_{max}.
Help the minister to find such
v_{0} value, that the number of traffic lights to switch to the "always green" mode is minimum. If
v_{0} is not uniquely defined, choose the maximum possible value of
v_{0}.
Input
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} ≤
s1, 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.
Output
On the first line, print the sought value
v_{0} 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_{0}. 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.
Example(s)
sample input

sample output

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

16.7000000000
0

sample input

sample output

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

25.0000000000
0

sample input

sample output

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

20.0400000000
1
2
