1. Abridged problem statement

There are n traffic lights on a street. Light i is at distance x_i and has a periodic cycle: green for g_i seconds, then red for r_i seconds, repeating with period c_i = r_i + g_i. The value d_i is the smallest t >= 0 when the light switches from green to red.

The King starts at position 0 at time 0 and drives at a constant speed v0 constrained by vmin <= v0 <= vmax. He passes light i at time t_i = x_i / v0. Passing exactly at a switching moment is allowed (counts as not red).

We are allowed to switch any subset of lights into "always green". Choose v0 to minimize the number of lights that would be red when the King passes; if multiple v0 give the same minimum, choose the maximum such v0. Output that v0, the number of switched lights, and their indices.

---

2. Detailed editorial (how the solution works)

A. Characterizing "green" times for one traffic light

For light i, period c = r_i + g_i.

Given d_i is a time when it changes green -> red, green intervals in each cycle k (integer) are:

    t in [d_i - g_i + k*c, d_i + k*c]

(Endpoints included because switching time is allowed.)

The King passes at time t = x_i / v.

So the condition "passes on green" becomes:

    x_i / v in [d_i - g_i + k*c, d_i + k*c]

Inverting (since v = x/t decreases in t), this gives a speed interval per cycle:

    v in [x_i / (d_i + k*c), x_i / (d_i - g_i + k*c)]

---

B. Reduce the global optimization to "maximum overlap of intervals"

If we pick a speed v, the number of lights that are green equals the number of these intervals (over all lights and all k) that contain v.

Minimizing the number of lights to switch to always green is equivalent to maximizing the number of lights that are already green:

    switches(v) = n - greenCount(v)

So we want to maximize greenCount(v) over v in [vmin, vmax], tie-breaking by choosing the maximum such v.

This becomes an interval stabbing / sweep-line problem.

---

C. Enumerating only relevant cycles k

For a light at x, the pass time range due to speed bounds is:

    t in [x/vmax, x/vmin]

We only need cycles whose green interval intersects that time range. We enumerate k = 0, 1, 2, ... and stop once gs = d - g + k*c > x/vmin.

Then we intersect times:
    t_lo = max(gs, x/vmax),  t_hi = min(ge, x/vmin)

If t_lo <= t_hi, convert to speed interval:
    v in [x/t_hi, x/t_lo]

Finally clamp to [vmin, vmax].

---

D. Sweep line on interval endpoints (events)

We build events:
- at interval left endpoint L: +1
- at interval right endpoint R: -1

Sort by position. At the same coordinate, process +1 before -1 (endpoints are inclusive).

Update the best when:
- cnt > best_cnt, or
- cnt == best_cnt and pos > best_v (tie-break: maximum speed)

---

E. Recover which lights must be switched at best_v

For each light, compute pass time t = x_i / best_v.

Compute the phase in [0, c):
    rem = (t - d_i + g_i) mod c

- If rem in [0, g_i] => green
- Else => red (must be switched)

The implementation uses fmod with epsilons to handle floating point issues.

---

F. Complexity

Let M be the total number of generated intervals. Then:

- interval generation: O(M)
- sorting events: O(M log M)
- final check over lights: O(n)

With constraints (n < 20000, vmin..vmax in 10..50, r, g in 10..20), the number of k per light is small.

---

3. C++ Solution

```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;
}
```

---

4. Python Solution (same approach) 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()
```

---

5. Compressed editorial

For each light i, green in cycle k occurs at times
[d_i - g_i + k*c_i, d_i + k*c_i] where c_i = r_i + g_i. With constant speed v, passing time is t = x_i/v. So for fixed k:

    x_i/v in [A,B] iff v in [x_i/B, x_i/A]

Intersect with allowed speeds [vmin, vmax]. Enumerate k while A <= x_i/vmin; skip invalid/negative intervals and compute the clamped speed interval [L,R]. Collect all such intervals over all lights.

Now choose v covered by the maximum number of intervals (maximizes green lights, minimizes switches). Do sweep-line on endpoints: add event (L,+1), (R,-1), sort by coordinate and process +1 before -1 at same coordinate; update best by coverage, tie-breaking by larger v.

Finally, for chosen best_v, for each light compute t = x_i/best_v, phase rem = (t - d_i + g_i) mod c_i; green iff rem in [0,g_i]. Output indices that are red (must be switched).
