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 is-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 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 minv 0v 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.

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 minv 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 is-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 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.

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