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

349. Wolves and Sheep
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The herds of Berland are in danger! Wolves have attacked a pasture of sheep. The shepherd has decided to exterminate wolves in the neighborhood without causing any damage to the sheep. Thus he took a trophy gun, left to him by his grandfather and headed for the ambush. The gun is cast steel and fires with the armour-piercing shells, and the bullets go right through and can hurt a sheep if a wolf is being shot. The wolves and the sheep are represented by segments. The shepherd is in point (0, 0). The flying path of a bullet is a ray coming from point (0, 0). If the path and the segment, characterizing an animal, intersect — the animal dies. Please find the minimum of shots, that is necessary, to kill all the wolves. We rely upon your prudence, for every sheep should remain safe and sound.

Input
The first line describes two integers N and M (0 ≤ N ≤ 105; 0 ≤ M ≤ 105) — is the amount of the wolves and the sheep accordingly. It is followed by N + M lines. Every line contains four integer numbers X1, Y1, X2, Y2 (-1000 ≤ X1, X2 ≤ 1000; 1 ≤ Y1, Y2 ≤ 1000), describing the segments. The first N lines describe the disposition of the wolves, the following M lines reveal the situation with the sheep. Segments can degenerate to points.

Output
Print the minimum amount of shots required to kill all the wolves. If you find this request quite impossible to fulfill without killing a single sheep, enter "No solution" (no quotation marks).

Example(s)
sample input
sample output
1 1
5 5 6 7
3 5 8 5
No solution

sample input
sample output
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999
1

<|response|>
1. Abridged problem statement
   You stand at the origin (0, 0). There are N wolves and M sheep, each represented by a line segment entirely in the half-plane y ≥ 1. A single shot is a ray from the origin in some direction; it kills every animal whose segment it intersects. However, you must not hit any sheep. Determine the minimum number of shots needed to kill all wolves without intersecting any sheep. If it’s impossible, print “No solution.”

2. Key observations
   • Any segment above the x-axis is “visible” from the origin over a continuous range of angles.
   • Compute the angular interval [α, β] for each segment, where α = atan2(y₁, x₁), β = atan2(y₂, x₂), sorted so α ≤ β.
   • A shot at angle θ kills exactly those segments whose angular interval contains θ.
   • Because every endpoint has y ≥ 1, all angles are strictly positive (between 0 and π), so there is no wrap-around and we can simply sort by angle starting from 0.
   • Sheep intervals become forbidden angle ranges: you can never choose θ inside any merged sheep interval.
   • Wolves intervals are the target ranges: you need to pick angles so that every wolf interval contains at least one chosen angle, and no chosen angle falls into a forbidden sheep interval.
   • This reduces to a “minimum stabbing points” problem on the real line with forbidden gaps. The classic greedy is: sort intervals by their right endpoint and, for each interval not yet stabbed, place a stabbing point as far right as possible (within that interval and not in any forbidden gap).

3. Full solution approach
   Step A: Read input, convert each segment to an angular interval.
     – For each segment endpoint (x, y), compute θ = atan2(y, x).
     – Build interval [min(θ₁, θ₂), max(θ₁, θ₂)].

   Step B: Merge sheep intervals into non-overlapping forbidden intervals.
     – Sort all sheep intervals by their start.
     – Sweep them, merging any that overlap or touch (within an epsilon).

   Step C: Sort wolf intervals by their right endpoint (ascending).

   Step D: Greedy stabbing with forbidden gaps.
     – Maintain a pointer into the merged sheep list (pos_sheep) and the last chosen shot angle (last, initialized to –∞).
     – For each wolf interval [wl, wr] in sorted order:
       • If last ≥ wl, this wolf is already covered—continue.
       • Advance pos_sheep until sheep[pos_sheep].end ≥ wr (we skip any forbidden interval that ends before the wolf’s right edge).
       • Tentatively set shot = wr (the rightmost possible).
       • If pos_sheep points to a sheep interval, we must avoid it, so set shot = min(shot, sheep[pos_sheep].start – ε).
       • If shot < wl, we cannot place any valid shot inside [wl, wr]—answer “No solution.”
       • Otherwise, record last = shot, increment shot count.

   Step E: Output the shot count if all wolves get covered.

   Complexity:
     – Converting and sorting intervals: O((N+M) log(N+M)).
     – Merging sheep intervals: O(M).
     – One pass over wolves and sheep pointers: O(N+M).
     – Total O((N+M) log(N+M)), suitable for N,M up to 10⁵.

4. C++ implementation
```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;
};

const double eps = 1e-9;

int n, m;
vector<pair<double, double>> wolves, sheep;

void read() {
    cin >> n >> m;
    wolves.resize(n);
    sheep.resize(m);
    for(auto& [alpha, beta]: wolves) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        alpha = atan2((double)y1, (double)x1);
        beta = atan2((double)y2, (double)x2);
        if(alpha > beta) {
            swap(alpha, beta);
        }
    }
    for(auto& [alpha, beta]: sheep) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        alpha = atan2((double)y1, (double)x1);
        beta = atan2((double)y2, (double)x2);
        if(alpha > beta) {
            swap(alpha, beta);
        }
    }
}

void solve() {
    // Convert 2D problem to 1D angle ranges and use greedy approach:
    // Union overlapping sheep ranges, sort wolves by right endpoint,
    // greedily place each wolf as far right as possible without hitting sheep.
    //
    // Note that in this problem we have Y >= 1, meaning that all angles will be
    // positive. It also means that we don't actually need to look at all
    // rotations to run the greedy for, and we can simply sort by atan2 angle
    // starting from 0.0.

    if(!sheep.empty()) {
        sort(sheep.begin(), sheep.end());
        vector<pair<double, double>> merged;
        auto current = sheep[0];

        for(int i = 1; i < (int)sheep.size(); i++) {
            if(sheep[i].first <= current.second + eps) {
                current.second = max(current.second, sheep[i].second);
            } else {
                merged.push_back(current);
                current = sheep[i];
            }
        }
        merged.push_back(current);
        sheep = merged;
    }

    sort(wolves.begin(), wolves.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    int pos_sheep = 0;
    double last = -1e9;
    int count = 0;

    for(auto& wolf: wolves) {
        if(wolf.first < last + eps) {
            continue;
        }

        while(pos_sheep < (int)sheep.size() &&
              wolf.second > sheep[pos_sheep].second) {
            pos_sheep++;
        }

        double rightmost = wolf.second;
        if(pos_sheep < (int)sheep.size()) {
            rightmost = min(rightmost, sheep[pos_sheep].first - eps);
        }

        if(rightmost < wolf.first - eps) {
            cout << "No solution\n";
            return;
        }

        last = rightmost;
        count++;
    }

    cout << count << "\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation
```python
import sys
import math

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    wolves = []
    sheep = []

    # Read a segment and convert to angular interval [a,b]
    def read_interval():
        x1, y1, x2, y2 = int(next(it)), int(next(it)), int(next(it)), int(next(it))
        a = math.atan2(y1, x1)
        b = math.atan2(y2, x2)
        return (min(a,b), max(a,b))

    for _ in range(N):
        wolves.append(read_interval())
    for _ in range(M):
        sheep.append(read_interval())

    # Merge overlapping sheep intervals into forbidden zones
    sheep.sort()
    merged = []
    EPS = 1e-9
    for seg in sheep:
        if not merged or seg[0] > merged[-1][1] + EPS:
            # No overlap, start a new forbidden interval
            merged.append([seg[0], seg[1]])
        else:
            # Overlaps or touches: extend the last one
            merged[-1][1] = max(merged[-1][1], seg[1])
    sheep = merged

    # Sort wolves by their right endpoint for the greedy algorithm
    wolves.sort(key=lambda x: x[1])

    last_shot = -1e18   # angle of the last shot fired
    shots = 0
    pos_sheep = 0
    S = len(sheep)

    for wl, wr in wolves:
        # If this wolf is already covered, skip
        if wl <= last_shot + EPS:
            continue

        # Advance sheep pointer past any whose end < wr
        while pos_sheep < S and sheep[pos_sheep][1] < wr - EPS:
            pos_sheep += 1

        # Try to shoot at wr (the rightmost possible)
        shoot = wr
        # If the next sheep interval starts ≤ wr, step back just before it
        if pos_sheep < S and sheep[pos_sheep][0] <= wr + EPS:
            shoot = min(shoot, sheep[pos_sheep][0] - EPS)

        # If that lies left of wl, no valid shot is possible
        if shoot < wl - EPS:
            print("No solution")
            return

        # Place the shot and cover this wolf
        last_shot = shoot
        shots += 1

    print(shots)

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