<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 ≤ xi ≤ s-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 vmin ≤ v0 ≤ vmax.

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.

Input
The first line of the input data contains four integers n, s, vmin and vmax (1 ≤ n < 20000, 1 ≤ s ≤ 20000, 10 ≤ vmin ≤ vmax ≤ 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 ≤ xi ≤ s-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.

Output
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.

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

<|response|>
1. Abridged problem statement

There are n traffic lights on a street segment. Light i is at distance x_i from the start. It alternates green for g_i seconds and red for r_i seconds, repeating forever with period c_i = r_i + g_i. The value d_i is the smallest time t >= 0 when it switches from green to red.

The King starts at time 0 from position 0 and drives at constant speed v where vmin <= v <= vmax. He reaches light i at time t = x_i / v. Passing exactly at a switch moment is allowed (counts as "not red").

We may switch any subset of lights into "always green". Choose a speed v0 in [vmin, vmax] that minimizes how many lights would be red at their pass time (those are switched). If multiple speeds achieve the same minimum, choose the maximum such speed. Output v0 (>=10 digits after decimal), count of switched lights, and their indices.

---

2. Key observations

1. Green time windows are periodic intervals.
   Since d_i is a green->red switch, for each integer cycle k, the green interval is:
   t in [d_i - g_i + k*c_i, d_i + k*c_i]
   (endpoints included).

2. A time interval converts to a speed interval.
   The King reaches light i at time t = x_i / v. For a fixed green window [A,B] with A>0, the condition x_i/v in [A,B] is equivalent to:
   v in [x_i/B, x_i/A]
   (because v = x/t decreases as t increases).

3. Optimization becomes "maximum overlap of intervals".
   For every light and every cycle k that matters, we get a speed interval where that light is green.
   For any speed v, the number of lights green equals the number of intervals covering v.
   Minimizing switched lights is equivalent to maximizing green lights.

4. We only need finitely many cycles per light.
   With speed bounds, the pass time for light i must be in:
   [x_i/vmax, x_i/vmin]
   We only enumerate cycles whose green interval intersects this time range.

5. Sweep line on endpoints finds best speed, tie-breaking by maximum speed.
   Create events (L, +1) and (R, -1) for each interval [L,R].
   Sort by coordinate; at the same coordinate process +1 before -1 (endpoints are inclusive).
   Track maximum active intervals; for ties pick larger coordinate.

---

3. Full solution approach

Step A - Generate all "good speed" intervals

For each light i:
- c = r_i + g_i
- Green in cycle k is [gs, ge] where:
  - gs = d_i - g_i + k*c
  - ge = d_i + k*c

We only care about times that can occur under speed limits:
- feasible pass time window is [x_i/vmax, x_i/vmin]

Intersect [gs, ge] with that feasible time window:
- t_lo = max(gs, x_i/vmax)
- t_hi = min(ge, x_i/vmin)
If t_lo <= t_hi, then converting to speed gives:
v in [x_i/t_hi, x_i/t_lo]
Clamp it into [vmin, vmax] and, if non-empty, keep it.

We enumerate k = 0,1,2,... and stop once gs > x_i/vmin.

Each kept interval [L,R] yields two sweep events:
- (L, +1)
- (R, -1)

Step B - Find speed with maximum interval coverage (sweep line)

Sort events by:
1) coordinate ascending
2) for same coordinate, +1 before -1

Sweep through unique coordinates:
- apply all +1 at this coordinate
- now active count = coverage at this point, update best:
  - if strictly larger coverage -> take it
  - if equal coverage and coordinate larger -> take it (tie-break: maximum speed)
- apply all -1 at this coordinate

This yields best_v.

Step C - Recover which lights are red at best_v

For each light i compute t = x_i / best_v. Determine whether t is in green.

Green windows are:
[d_i - g_i + k*c, d_i + k*c]
Shift time so that green starts at phase 0:
rem = (t - d_i + g_i) mod c
Then:
- green iff rem in [0, g_i] (inclusive)
- otherwise red => must be switched

Use a small epsilon for floating-point stability.

Complexity

Let M be total generated intervals. Then:
- generating intervals: O(M)
- sorting events: O(M log M)
- checking all lights at best_v: O(n)

With constraints (vmax <= 50, r,g <= 20), each light contributes only a small number of cycles, so this runs fast.

---

4. C++ implementation with comments

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, s, v_min, v_max;
vector<int> xi, ri, gi, di;

void read() {
    cin >> n >> s >> v_min >> v_max;
    xi.resize(n);
    ri.resize(n);
    gi.resize(n);
    di.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> xi[i] >> ri[i] >> gi[i] >> di[i];
    }
}

void solve() {
    // To have a green wave, for each traffic light we want the time we pass
    // ti = xi / v0, to be withing the green periods, or:
    //
    //        ti   \in [di - gi + k*(gi+ri)  ; di + k*(gi+ri)            ].
    //
    //     xi / v0 \in [di - gi + k*(gi+ri)  ; di + k*(gi+ri)            ].
    //
    //        v0   \in [xi / (di + k*(gi+ri)); xi / (di - gi + k*(gi+ri))].
    //
    // This means that the range of v0 will be the union or some ranges. If we
    // could compactly encode the set of v0, we could do a DP[traffic
    // light][set of v0 that are available]. The issue is that the set above
    // depends on k, and it's a floating point number. However, we can notice
    // that it's enough to notice that it's always possible for the v0 to lie on
    // a border of one of these ranges. Then it's clear which traffic lights we
    // violated and which we don't. In terms of candidates, we know that the
    // candidates have 10 <= v0 <= 50, so for any i, there are less than ~50
    // possible values for k, or overall that's around a million. This directly
    // gives us a O(#candidates * n) solution, but instead we can notice that
    // for each traffic light i, the ranges are non-overlapping. This means we
    // can instead think of this problem as having some points P, and ranges
    // L,R, and figuring out the point that is covered by the largest number of
    // ranges. This can be done by maintaining an array offline with +1 on L and
    // -1 on (R+1). We should compress the coordinates too.

    vector<pair<double, int>> events;

    for(int i = 0; i < n; i++) {
        int c = ri[i] + gi[i];
        for(int k = 0;; k++) {
            int gs = di[i] - gi[i] + k * c;
            int ge = di[i] + k * c;

            if((double)gs > (double)xi[i] / v_min) {
                break;
            }
            if(ge <= 0) {
                continue;
            }
            if((double)xi[i] / ge > (double)v_max) {
                continue;
            }

            double t_lo = max((double)gs, xi[i] / (double)v_max);
            double t_hi = min((double)ge, xi[i] / (double)v_min);
            if(t_lo < 1e-15) {
                t_lo = 1e-15;
            }
            if(t_lo > t_hi + 1e-12) {
                continue;
            }

            double vl = xi[i] / t_hi;
            double vh = xi[i] / t_lo;
            vl = max(vl, (double)v_min);
            vh = min(vh, (double)v_max);
            if(vl > vh + 1e-12) {
                continue;
            }

            events.push_back({vl, 1});
            events.push_back({vh, -1});
        }
    }

    sort(
        events.begin(), events.end(),
        [](const pair<double, int>& a, const pair<double, int>& b) {
            if(a.first != b.first) {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    );

    int cnt = 0, best_cnt = 0;
    double best_v = v_max;

    for(int i = 0; i < (int)events.size();) {
        double pos = events[i].first;
        while(i < (int)events.size() && events[i].first == pos &&
              events[i].second > 0) {
            cnt++;
            i++;
        }
        if(cnt > best_cnt || (cnt == best_cnt && pos > best_v)) {
            best_cnt = cnt;
            best_v = pos;
        }
        while(i < (int)events.size() && events[i].first == pos &&
              events[i].second < 0) {
            cnt--;
            i++;
        }
    }

    const double eps = 1e-9;
    vector<int> switched;
    for(int i = 0; i < n; i++) {
        double t = xi[i] / best_v;
        int c = ri[i] + gi[i];
        double rem = fmod(t - di[i] + gi[i], (double)c);
        if(rem < -eps) {
            rem += c;
        }
        if(rem > gi[i] + eps && rem < c - eps) {
            switched.push_back(i + 1);
        }
    }

    cout << fixed << setprecision(10) << best_v << "\n";
    cout << switched.size() << "\n";
    for(int i = 0; i < (int)switched.size(); i++) {
        if(i) {
            cout << " ";
        }
        cout << switched[i];
    }
    if(!switched.empty()) {
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

5. Python implementation with detailed comments

```python
import sys, math

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    s = int(next(it))      # not used in computations; lights are within [1, s-1]
    vmin = int(next(it))
    vmax = int(next(it))

    x = [0]*n
    r = [0]*n
    g = [0]*n
    d = [0]*n
    for i in range(n):
        x[i] = int(next(it))
        r[i] = int(next(it))
        g[i] = int(next(it))
        d[i] = int(next(it))

    # We will collect sweep events (position, delta):
    # +1 at interval start, -1 at interval end.
    events = []

    for i in range(n):
        c = r[i] + g[i]  # cycle length

        # Enumerate cycle index k while there can still be intersection
        k = 0
        while True:
            gs = d[i] - g[i] + k * c  # green start time in this cycle
            ge = d[i] + k * c         # green end time in this cycle (inclusive)

            # Latest arrival time allowed by min speed
            if float(gs) > x[i] / vmin:
                break

            # If green interval ends at non-positive time, skip
            if ge <= 0:
                k += 1
                continue

            # If to arrive by time ge we would need speed > vmax, skip
            if x[i] / ge > vmax:
                k += 1
                continue

            # Feasible arrival times given speed limits
            # t in [x/vmax, x/vmin]
            t_lo = max(float(gs), x[i] / vmax)
            t_hi = min(float(ge), x[i] / vmin)

            # Avoid division by 0 and negative due to numeric corner cases
            if t_lo < 1e-15:
                t_lo = 1e-15

            # If no intersection, skip
            if t_lo > t_hi + 1e-12:
                k += 1
                continue

            # Convert time window to speed window: v = x / t
            vl = x[i] / t_hi
            vh = x[i] / t_lo

            # Clamp to [vmin, vmax]
            if vl < vmin:
                vl = float(vmin)
            if vh > vmax:
                vh = float(vmax)

            # If interval is empty after clamping, skip
            if vl > vh + 1e-12:
                k += 1
                continue

            events.append((vl, +1))
            events.append((vh, -1))

            k += 1

    # Sort: by position ascending; for equal positions, +1 before -1
    events.sort(key=lambda p: (p[0], -p[1]))

    cnt = 0
    best_cnt = 0
    best_v = float(vmax)  # tie-break wants maximum v

    i = 0
    m = len(events)
    while i < m:
        pos = events[i][0]

        # Apply all starts at this pos
        while i < m and events[i][0] == pos and events[i][1] > 0:
            cnt += 1
            i += 1

        # Update best (tie-break by larger pos)
        if cnt > best_cnt or (cnt == best_cnt and pos > best_v):
            best_cnt = cnt
            best_v = pos

        # Apply all ends at this pos
        while i < m and events[i][0] == pos and events[i][1] < 0:
            cnt -= 1
            i += 1

    # Determine which lights are red at best_v
    eps = 1e-9
    switched = []
    for i in range(n):
        t = x[i] / best_v
        c = r[i] + g[i]

        # Phase relative to green start:
        # green start at times d-g + k*c, so shift by (-d+g)
        rem = math.fmod(t - d[i] + g[i], c)
        if rem < -eps:
            rem += c

        # If strictly inside red (with epsilon margins), mark to switch
        if rem > g[i] + eps and rem < c - eps:
            switched.append(i + 1)  # 1-based index

    # Output
    sys.stdout.write(f"{best_v:.10f}\n")
    sys.stdout.write(f"{len(switched)}\n")
    if switched:
        sys.stdout.write(" ".join(map(str, switched)) + "\n")

if __name__ == "__main__":
    solve()
```
