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 xi, ri, gi, di, which stand for:
  • xi — the distance from the beginning of the street to the traffic light (1 ≤ xis-1),
  • ri — the duration of the red light illumination (10 ≤ ri ≤ 20),
  • gi — the duration of the green light illumination (10 ≤ gi ≤ 20),
  • di — the minimum non-negative moment of time when the traffic light changes the light from green to red (0 ≤ di < ri+gi).

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 v0 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 v0 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 vmax. On the other hand, the King will be angry if the recommended speed is less than vmin. Thus, the minister should choose such value of v0, which satisfies the inequation vminv0vmax.

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

The first line of the input data contains four integers n, s, vmin and vmax (1 ≤ n < 20000, 1 ≤ s ≤ 20000, 10 ≤ vminvmax ≤ 50), where n is the number of traffic lights on the street, s is the length of the street in meters, vmin and vmax 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 xi, ri, gi, di (1 ≤ xis-1, 10 ≤ ri,gi ≤ 20, 0 ≤ di < ri+gi), where xi, ri, gi, di are explained above. Values ri, gi, di are given in seconds and xi — in meters. No two traffic lights are located at one point.

On the first line, print the sought value v0 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 v0. 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.

sample input
sample output
3 1000 10 30
500 10 10 10
501 10 10 0
600 10 10 0

sample input
sample output
2 1000 10 30
500 10 10 10
600 10 20 2

sample input
sample output
4 1000 10 30
800 10 15 20
500 20 10 15
501 20 10 5
600 10 20 15