<|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 ∈ [A,B]` is equivalent to:
   \[
   v \in \left[\frac{x_i}{B},\; \frac{x_i}{A}\right]
   \]
   (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 ⇔ maximizing green lights.

4. **We only need finitely many cycles per light.**  
   With speed bounds, the pass time for light `i` must be in:
   \[
   \left[\frac{x_i}{vmax},\; \frac{x_i}{vmin}\right]
   \]
   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 \left[\frac{x_i}{t_{hi}},\; \frac{x_i}{t_{lo}}\right]
\]
Clamp it into `[vmin, vmax]` and, if non-empty, keep it.

We enumerate `k = 0,1,2,...` and stop once `gs > x_i/vmin` (then future `gs` only increase, so no further intersections are possible).

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) \bmod c
\]
Then:
- green iff `rem ∈ [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 (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Traffic Lights (p540) solution.

  Idea:
  - For each light i and each cycle k, compute speed intervals where we pass on green.
  - Collect all such speed intervals inside [vmin, vmax].
  - Find a speed covered by maximum number of intervals (sweep line).
  - Tie-break: choose maximum speed among best.
  - Finally, compute which lights are red at that speed -> must switch.
*/

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

    int n, s, vmin, vmax;
    cin >> n >> s >> vmin >> vmax;

    vector<int> x(n), r(n), g(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> r[i] >> g[i] >> d[i];
    }

    // Sweep events: (position, delta)
    // For interval [L, R] inclusive:
    //   event (L, +1) means interval becomes active
    //   event (R, -1) means interval stops being active AFTER point R is considered
    vector<pair<double,int>> events;
    events.reserve(n * 20); // rough guess, not required

    for (int i = 0; i < n; i++) {
        int c = r[i] + g[i];

        // Enumerate cycles k while green-start is not beyond latest possible arrival time.
        for (int k = 0;; k++) {
            int gs = d[i] - g[i] + k * c; // green start time
            int ge = d[i] + k * c;        // green end time (green->red switch), inclusive

            // Latest possible arrival time at this light if driving at vmin:
            // if green start is after that, no further k can work.
            if ((double)gs > (double)x[i] / vmin) break;

            // If green interval is entirely at non-positive time, ignore.
            if (ge <= 0) continue;

            // If even arriving by time ge requires speed > vmax, then this cycle doesn't help.
            // (Because v = x/t, so to have x/v <= ge means v >= x/ge.
            //  If x/ge > vmax, cannot.)
            if ((double)x[i] / ge > (double)vmax) continue;

            // Feasible arrival times due to speed bounds are:
            // t in [x/vmax, x/vmin]
            double t_lo = max((double)gs, x[i] / (double)vmax);
            double t_hi = min((double)ge, x[i] / (double)vmin);

            // Avoid dividing by zero (or negative due to numeric corner cases).
            if (t_lo < 1e-15) t_lo = 1e-15;

            // Empty intersection => no speed works for this (i,k).
            if (t_lo > t_hi + 1e-12) continue;

            // Convert time interval [t_lo, t_hi] to speed interval:
            // v = x/t => v in [x/t_hi, x/t_lo] (note reversed).
            double L = x[i] / t_hi;
            double R = x[i] / t_lo;

            // Clamp to [vmin, vmax]
            L = max(L, (double)vmin);
            R = min(R, (double)vmax);

            if (L > R + 1e-12) continue;

            events.push_back({L, +1});
            events.push_back({R, -1});
        }
    }

    // Sort by coordinate; for ties, +1 before -1 so endpoints are counted as covered.
    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; // +1 first
         });

    int active = 0;
    int bestActive = -1;
    double bestV = (double)vmax; // tie-break wants maximum speed

    // Sweep through unique coordinates.
    for (int i = 0; i < (int)events.size(); ) {
        double pos = events[i].first;

        // Apply all starts at pos.
        while (i < (int)events.size() && events[i].first == pos && events[i].second == +1) {
            active++;
            i++;
        }

        // Now "active" equals coverage at v = pos.
        // Update best: maximize coverage; tie-break by larger v.
        if (active > bestActive || (active == bestActive && pos > bestV)) {
            bestActive = active;
            bestV = pos;
        }

        // Apply all ends at pos.
        while (i < (int)events.size() && events[i].first == pos && events[i].second == -1) {
            active--;
            i++;
        }
    }

    // Determine which lights are red at bestV (must be switched to always green).
    const double eps = 1e-9;
    vector<int> switched;
    switched.reserve(n);

    for (int i = 0; i < n; i++) {
        double t = x[i] / bestV;  // passing time
        int c = r[i] + g[i];

        // Compute phase relative to green start.
        // Green start times are (d - g + k*c).
        // So shift by (-d + g) and take mod c.
        double rem = fmod(t - d[i] + g[i], (double)c);
        if (rem < -eps) rem += c; // normalize to [0, c)

        // Green iff rem in [0, g] (inclusive). Otherwise red.
        if (rem > g[i] + eps && rem < c - eps) {
            switched.push_back(i + 1); // 1-based index
        }
    }

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

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import math

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)

    n = int(next(it))
    s = int(next(it))      # not needed for computations
    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))

    # Collect interval endpoint events: (pos, delta)
    # Interval [L, R] inclusive => (L, +1), (R, -1)
    events = []

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

        k = 0
        while True:
            gs = d[i] - g[i] + k * c  # green start (time)
            ge = d[i] + k * c         # green end (time), inclusive

            # If green start is after latest possible arrival time (x/vmin), stop.
            if float(gs) > x[i] / vmin:
                break

            # Ignore cycles that end at non-positive time.
            if ge <= 0:
                k += 1
                continue

            # If arriving by ge requires speed > vmax, impossible for this cycle.
            if x[i] / ge > vmax:
                k += 1
                continue

            # Intersect with feasible arrival times [x/vmax, x/vmin].
            t_lo = max(float(gs), x[i] / vmax)
            t_hi = min(float(ge), x[i] / vmin)

            # Prevent division by zero.
            if t_lo < 1e-15:
                t_lo = 1e-15

            if t_lo > t_hi + 1e-12:
                k += 1
                continue

            # Convert time window to speed window v = x/t.
            L = x[i] / t_hi
            R = x[i] / t_lo

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

            if L <= R + 1e-12:
                events.append((L, +1))
                events.append((R, -1))

            k += 1

    # Sort events by coordinate, and for equal coordinate process +1 before -1.
    events.sort(key=lambda p: (p[0], -p[1]))

    active = 0
    best_active = -1
    best_v = float(vmax)  # tie-break wants maximum speed

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

        # apply all starts
        while i < m and events[i][0] == pos and events[i][1] == +1:
            active += 1
            i += 1

        # coverage at v = pos
        if active > best_active or (active == best_active and pos > best_v):
            best_active = active
            best_v = pos

        # apply all ends
        while i < m and events[i][0] == pos and events[i][1] == -1:
            active -= 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
        rem = math.fmod(t - d[i] + g[i], c)
        if rem < -eps:
            rem += c

        # green iff rem in [0, g]; otherwise red
        if rem > g[i] + eps and rem < c - eps:
            switched.append(i + 1)

    out = []
    out.append(f"{best_v:.10f}\n")
    out.append(f"{len(switched)}\n")
    if switched:
        out.append(" ".join(map(str, switched)) + "\n")
    sys.stdout.write("".join(out))

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

If you want, I can also add notes on numeric robustness (endpoint inclusiveness, epsilon choices) and why the sweep evaluates only event coordinates but still yields a correct “maximum speed” tie-break.