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

150. Mr. Beetle II
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



There is a small beetle living on infinite checkered sheet. Size of each cell is 1x1, the axes of Cartesian coordinate system are lying on the border of cells. Early in the morning beetle travels from his house at point (x1,y1) to the point (x2,y2). All cells that he passed are numbered in order of passing (borders and corners of cells are not considered to be parts of cells). You need to find coordinates of left lower corner of n-th cell on the way of Mr Beetle.

Input
Input consists of integers x1,y1,x2,y2,n (1<=n<=10^5) written in one line. All coordinates are not greater than 10^6 by it's absolute values.

Output
Write two numbers, separated by space: coordinates of left most lower point of n-th cell in the beetle's way. If such cell doesn't exist then write 'no solution'.

Sample test(s)

Input
2 3 4 -1 3

Output
3 0
Author:	Michael R. Mirzayanov
Resource:	Saratov Subregional School Team Contest, 2002
Date:	Spring, 2002

<|response|>
## 1) Abridged problem statement

A beetle moves along the straight line segment from \((x_1,y_1)\) to \((x_2,y_2)\) on an infinite grid of **unit square cells** whose borders lie on integer coordinates.  
A cell is considered “passed” if the segment intersects the **interior** of the cell (touching only borders/corners does **not** count). Cells are numbered in the order the beetle passes them.

Given \(n\), output the integer coordinates \((X,Y)\) of the **lower-left corner** of the \(n\)-th passed cell, or print `no solution` if fewer than \(n\) cells are passed.

Constraints: \(1 \le n \le 10^5\), \(|x_i|,|y_i| \le 10^6\), inputs are integers.

---
## 2) Key observations needed to solve the problem

1. **Each cell corresponds to integer indices \((c_x,c_y)\)** and represents the open square:
   \[
   (c_x, c_x+1)\times(c_y, c_y+1)
   \]
   “Passed” means the segment intersects this open square (interior only); touching only borders or corners does not count.

2. The segment is parameterized as:
   \[
   P(t)=(x_1,y_1) + t(dx,dy),\quad t\in[0,1]
   \]
   where \(dx=x_2-x_1\), \(dy=y_2-y_1\). A cell is passed iff there exists \(t\in(0,1)\) with \(c_x < x(t) < c_x+1\) and \(c_y < y(t) < c_y+1\).

3. We only need up to \(n \le 10^5\) cells, so we do not have to walk the whole (possibly very long) segment. It suffices to gather a bounded pool of **candidate cells**, keep the ones the segment really crosses, and order them.

4. **Candidate generation by sampling.** Walk along the segment in steps of Euclidean length \(\approx 1\) (`dt = 1/|B-A|`). At each sample take the cell `floor(x), floor(y)` and add it together with its 8 neighbors (a 3×3 block). The neighborhood compensates for the coarse sampling: if the true crossed cell sits between two samples near a boundary, it is still one of the neighbors. We stop once we have collected about `8*n` candidates, which keeps the work \(O(n)\).

5. **Exact filtering.** Each candidate is verified by an exact integer slab test. For the open cell we intersect the \(t\)-interval where \(x(t)\in(c_x,c_x+1)\) with the one where \(y(t)\in(c_y,c_y+1)\) and with \([0,1]\); the cell is passed iff that intersection is a non-empty open interval (`t_min < t_max`, compared via cross-multiplication to avoid floating error). A zero `dx` (or `dy`) means the segment is axis-parallel, so the corresponding coordinate must already lie strictly inside the strip.

6. **Ordering.** Each surviving cell gets an entry parameter
   \[
   t_\text{entry} = \max\!\big(0,\ \min(t_{x1},t_{x2}),\ \min(t_{y1},t_{y2})\big),
   \]
   the earliest \(t\) where the line is inside both slabs. Sorting candidates by `t_entry` puts them in the order the beetle visits them; duplicates are then removed with `unique`.

7. **Degenerate segment.** If \(A=B\) the beetle does not move. Since inputs are integers the point lies on a grid line, so no interior cell is passed unless the point were strictly inside a cell; with integer input this gives `no solution` (and any `n>1` is impossible).

---

## 3) Full solution approach based on the observations

1. Read \(x_1,y_1,x_2,y_2,n\) and form \(A=(x_1,y_1)\), \(B=(x_2,y_2)\).
2. If \(|B-A|\approx 0\): handle the degenerate case as in observation 7 and stop.
3. Let `dt = 1/|B-A|`. Iterate `t = 0, dt, 2dt, ...` up to \(1\) (and while fewer than `8*n` candidates collected). For each sample compute the containing cell and push it plus its 3×3 neighborhood into a candidate list, after checking each candidate with the exact `intersects_cell` slab test.
4. Sort the candidate list by `t_entry` and `unique` it.
5. If the list has fewer than \(n\) cells, print `no solution`; otherwise print the lower-left corner of the \(n\)-th cell.

Complexity: candidate generation and filtering are \(O(n)\) with a small constant, comfortably within the limits.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

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

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }
};

int n;
Point a, b;

void read() { cin >> a >> b >> n; }

void solve() {
    // This is a simple problem - we can simply simulate the n steps, by walking
    // with distance 1.0 in the direction to x1,y1. We look at the 9 adjacent
    // cells, and keep a visited map to not over count (or we can just remove
    // the later on). When we get to N points, we will sort them by distance
    // from x1,y1. We have to be careful about precision issues, so we opt for
    // integer computation.

    Point dir = b - a;
    double len = dir.norm();
    constexpr double eps = 1e-9;

    if(len < eps) {
        bool on_boundary =
            abs(a.x - round(a.x)) < eps || abs(a.y - round(a.y)) < eps;
        if(on_boundary || n != 1) {
            cout << "no solution" << endl;
        } else {
            cout << (int)floor(a.x) << " " << (int)floor(a.y) << endl;
        }
        return;
    }

    vector<pair<int, int>> order;
    double dt = 1.0 / len;

    int x1 = (int)a.x, y1 = (int)a.y, x2 = (int)b.x, y2 = (int)b.y;
    int dx = x2 - x1, dy = y2 - y1;

    auto intersects_cell = [&](int ncx, int ncy) -> bool {
        int64_t t_min_num = 0, t_min_den = 1;
        int64_t t_max_num = 1, t_max_den = 1;

        if(dx != 0) {
            int64_t t1_num = ncx - x1, t2_num = ncx + 1 - x1;
            int64_t den = dx;
            if(den < 0) {
                t1_num = -t1_num;
                t2_num = -t2_num;
                den = -den;
            }
            if(t1_num > t2_num) {
                swap(t1_num, t2_num);
            }
            if(t1_num * t_min_den > t_min_num * den) {
                t_min_num = t1_num;
                t_min_den = den;
            }
            if(t2_num * t_max_den < t_max_num * den) {
                t_max_num = t2_num;
                t_max_den = den;
            }
        } else if(x1 <= ncx || x1 >= ncx + 1) {
            return false;
        }

        if(dy != 0) {
            int64_t t1_num = ncy - y1, t2_num = ncy + 1 - y1;
            int64_t den = dy;
            if(den < 0) {
                t1_num = -t1_num;
                t2_num = -t2_num;
                den = -den;
            }
            if(t1_num > t2_num) {
                swap(t1_num, t2_num);
            }
            if(t1_num * t_min_den > t_min_num * den) {
                t_min_num = t1_num;
                t_min_den = den;
            }
            if(t2_num * t_max_den < t_max_num * den) {
                t_max_num = t2_num;
                t_max_den = den;
            }
        } else if(y1 <= ncy || y1 >= ncy + 1) {
            return false;
        }

        return t_min_num * t_max_den < t_max_num * t_min_den;
    };

    auto get_entry_t = [&](int ncx, int ncy) -> double {
        double t_min = 0;
        if(dx != 0) {
            double t1 = (double)(ncx - x1) / dx;
            double t2 = (double)(ncx + 1 - x1) / dx;
            t_min = max(t_min, min(t1, t2));
        }
        if(dy != 0) {
            double t1 = (double)(ncy - y1) / dy;
            double t2 = (double)(ncy + 1 - y1) / dy;
            t_min = max(t_min, min(t1, t2));
        }
        return t_min;
    };

    for(double t = 0; t <= 1.0 + eps && (int)order.size() < 8 * n; t += dt) {
        double x = a.x + dir.x * t;
        double y = a.y + dir.y * t;
        int cx = (int)floor(x);
        int cy = (int)floor(y);

        for(int dcx = -1; dcx <= 1; dcx++) {
            for(int dcy = -1; dcy <= 1; dcy++) {
                int ncx = cx + dcx;
                int ncy = cy + dcy;
                if(intersects_cell(ncx, ncy)) {
                    order.push_back({ncx, ncy});
                }
            }
        }
    }

    sort(order.begin(), order.end(), [&](const auto& a, const auto& b) {
        return get_entry_t(a.first, a.second) < get_entry_t(b.first, b.second);
    });
    order.erase(unique(order.begin(), order.end()), order.end());

    if((int)order.size() < n) {
        cout << "no solution" << endl;
    } else {
        cout << order[n - 1].first << " " << order[n - 1].second << endl;
    }
}

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 (alternative: exact 2D DDA grid-walk)

The C++ above gathers candidates by sampling and filters them with an exact slab test. An equally valid and slightly simpler Python version walks the grid exactly with a 2D DDA (voxel traversal): from the first interior cell it repeatedly jumps to the next vertical or horizontal grid-line crossing, visiting cells in the exact order the segment passes them. Borders/corners are excluded by starting a tiny epsilon along the direction.

```python
import sys
import math

"""
Mr. Beetle II (p150) - Python
Exact grid traversal (2D DDA / voxel traversal).

We enumerate grid cells whose interiors are intersected by the segment,
in the correct order, and return the n-th one.

Important: borders/corners do not count. Since inputs are integers,
the segment starts on grid lines. We shift start by a tiny epsilon along
direction to land inside the first cell the segment actually enters.
"""

def solve():
    x1, y1, x2, y2, n = map(int, sys.stdin.read().split())

    # No movement: starting point is integer => on border => no interior cell
    if x1 == x2 and y1 == y2:
        print("no solution")
        return

    dx = x2 - x1
    dy = y2 - y1

    eps = 1e-12
    sx = x1 + eps * dx
    sy = y1 + eps * dy

    cx = math.floor(sx)
    cy = math.floor(sy)

    # Step direction: if dx>0 move right, else move left (dx != 0 case)
    step_x = 1 if dx > 0 else -1
    step_y = 1 if dy > 0 else -1

    # Next crossing times in parameter t in [0,1]
    if dx != 0:
        next_vline = (cx + 1) if step_x > 0 else cx
        t_max_x = (next_vline - sx) / dx
        t_delta_x = 1.0 / abs(dx)
    else:
        t_max_x = float("inf")
        t_delta_x = float("inf")

    if dy != 0:
        next_hline = (cy + 1) if step_y > 0 else cy
        t_max_y = (next_hline - sy) / dy
        t_delta_y = 1.0 / abs(dy)
    else:
        t_max_y = float("inf")
        t_delta_y = float("inf")

    visited = 0
    t = 0.0

    while True:
        visited += 1
        if visited == n:
            print(cx, cy)
            return

        # Advance to next grid boundary crossing
        if t_max_x < t_max_y:
            t = t_max_x
            if t >= 1.0 - 1e-15:
                break
            cx += step_x
            t_max_x += t_delta_x

        elif t_max_y < t_max_x:
            t = t_max_y
            if t >= 1.0 - 1e-15:
                break
            cy += step_y
            t_max_y += t_delta_y

        else:
            # Corner crossing: move diagonally
            t = t_max_x
            if t >= 1.0 - 1e-15:
                break
            cx += step_x
            cy += step_y
            t_max_x += t_delta_x
            t_max_y += t_delta_y

    print("no solution")


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

This DDA-based method is conceptually clean, avoids the sampling/neighbor heuristics, respects “open interior only”, and runs in \(O(n)\) time (stopping as soon as the \(n\)-th cell is found).