#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using i128 = __int128;

struct Point {
    ll x;
    ll y;

    Point() : x(0), y(0) {}
    Point(ll x_, ll y_) : x(x_), y(y_) {}

    Point operator-(const Point &other) const {
        return Point(x - other.x, y - other.y);
    }

    i128 operator%(const Point &other) const {
        return i128(x) * other.y - i128(y) * other.x;
    }

    i128 operator*(const Point &other) const {
        return i128(x) * other.x + i128(y) * other.y;
    }

    bool operator<(const Point &other) const {
        return make_pair(x, y) < make_pair(other.x, other.y);
    }

    void rotate45() {
        ll nx = x - y;
        ll ny = x + y;
        x = nx;
        y = ny;
    }

    bool operator==(const Point &) const = default;

    friend ostream &operator<<(ostream &out, const Point &pt) {
        return out << '(' << pt.x << ", " << pt.y << ')';
    }
};

enum class SegmentDirection : int {
    Left = 1,
    Right = 2,
};

string segment_direction_to_string(const SegmentDirection &direction) {
    if (direction == SegmentDirection::Left) {
        return "left";
    }
    return "right";
}

struct Segment {
    Point from;
    Point to;
    int poly_id;
    SegmentDirection direction;

    bool is_vertical() const {
        return from.x == to.x;
    }

    friend ostream &operator<<(ostream &out, const Segment &seg) {
        return out << '{' << seg.from << ", " << seg.to
                   << ", direction: " << segment_direction_to_string(seg.direction)
                   << ", poly_id: " << seg.poly_id << '}';
    }
};

bool inside_segment(const Point &a, const Point &b, const Point &p) {
    return (p - a) % (p - b) == 0 && (p - a) * (p - b) <= 0;
}

bool strictly_inside_segment(const Point &a, const Point &b, const Point &p) {
    return inside_segment(a, b, p) && a != p && b != p;
}

i128 triangle_double_area(const Point &a, const Point &b, const Point &c) {
    auto s = (b - a) % (c - a);
    // abs doesn't work for i128
    if (s < 0) {
        return -s;
    }
    return s;
}

bool strictly_inside_triangle(const Point &a, const Point &b, const Point &c, const Point &p) {
    if (inside_segment(a, b, p) || inside_segment(b, c, p) || inside_segment(c, a, p)) {
        return false;
    }
    return triangle_double_area(a, b, c) == triangle_double_area(a, b, p) +
                                                triangle_double_area(b, c, p) +
                                                triangle_double_area(c, a, p);
}

struct ConvexPolygon {
    vector<Point> p;
    int id = -1;

    ConvexPolygon() {}

    ConvexPolygon(const vector<Point> &p_, int id_) : p(p_), id(id_) {
        normalize();
    }

    i128 oriented_area() const {
        i128 s = 0;
        for (int i = 0; i < (int)p.size(); i++) {
            s += p[i] % p[(i + 1) % p.size()];
        }
        return s;
    }

    void normalize() {
        if (oriented_area() < 0) {
            reverse(p.begin(), p.end());
        }
        int pos = min_element(p.begin(), p.end()) - p.begin();
        rotate(p.begin(), p.begin() + pos, p.end());
        assert(oriented_area() > 0);
    }

    void rotate45() {
        for (auto &pt : p) {
            pt.rotate45();
        }
    }

    vector<Segment> to_segments() const {
        vector<Segment> segs;
        segs.reserve(p.size());
        for (int i = 0; i < (int)p.size(); i++) {
            Segment seg{
                .from = p[i],
                .to = p[(i + 1) % p.size()],
                .poly_id = id,
                .direction = SegmentDirection::Right,
            };
            if (seg.from.x > seg.to.x) {
                swap(seg.from, seg.to);
                seg.direction = SegmentDirection::Left;
            }
            segs.push_back(seg);
        }
        return segs;
    }

    bool check_point_stricktly_inside(const Point &pt) const {
        int lb = 1, rb = (int)p.size() - 1;
        while (rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if ((pt - p[0]) % (p[mid] - p[0]) >= 0) {
                rb = mid;
            } else {
                lb = mid;
            }
        }

        if (rb < (int)p.size() - 1 && strictly_inside_segment(p[0], p[rb], pt)) {
            return true;
        }
        return strictly_inside_triangle(p[0], p[lb], p[rb], pt);
    }
};

enum class EventType : int {
    Insert = 0,
    Delete = 1,
};

struct Event {
    EventType type;
    Segment seg;
};

ll X = 0;

bool compare(const Segment &lhs, const Segment &rhs) {
    ll lx1 = lhs.from.x;
    ll rx1 = lhs.to.x;
    ll length1 = rx1 - lx1;

    ll lx2 = rhs.from.x;
    ll rx2 = rhs.to.x;
    ll length2 = rx2 - lx2;

    ll dy1 = lhs.to.y - lhs.from.y;
    ll dy2 = rhs.to.y - rhs.from.y;

    ll y1 = lhs.from.y;
    ll y2 = rhs.from.y;

    // y + dy * (X - lx) / length

    auto lhs_value = i128(y1) * length1 * length2 + i128(length2) * dy1 * (X - lx1);
    auto rhs_value = i128(y2) * length1 * length2 + i128(length1) * dy2 * (X - lx2);

    if (lhs_value != rhs_value) {
        return lhs_value < rhs_value;
    }
    if (lhs.direction != rhs.direction) {
        return lhs.direction < rhs.direction;
    }
    if (lhs.from.y != rhs.from.y) {
        return lhs.from.y < rhs.from.y;
    }
    return lhs.poly_id < rhs.poly_id;
}

int sign(i128 val) {
    if (val < 0) {
        return -1;
    }
    if (val > 0) {
        return +1;
    }
    return 0;
}

bool strictly_intersects(Segment a, Segment b) {
    for (int _ : {0, 1}) {
        if (sign((b.from - a.from) % (b.to - a.from)) * sign((b.from - a.to) % (b.to - a.to)) !=
            -1) {
            return false;
        }
        if (sign((b.from - a.from) % (b.to - a.from)) * sign((b.from - a.to) % (b.to - a.to)) !=
            -1) {
            return false;
        }
        swap(a, b);
    }
    return true;
}

// return (-1, -1) if no intersection found
pair<int, int> find_intersections_with_fixed_direction(const vector<ConvexPolygon> &a) {
    map<ll, vector<Event>> events;
    for (const auto &p : a) {
        for (auto seg : p.to_segments()) {
            if (seg.is_vertical()) {
                continue;
            }
            events[seg.from.x].push_back(Event{
                .type = EventType::Insert,
                .seg = seg,
            });
            events[seg.to.x].push_back(Event{
                .type = EventType::Delete,
                .seg = seg,
            });
        }
    }

    set<Segment, decltype(&compare)> open(compare);

    // auto dump = [&]() {
    //     cerr << "\n\n-----\n";
    //     for (const auto &seg : open) {
    //         cout << seg << endl;
    //     }
    //     vector<Segment> f(open.begin(), open.end());
    //     for (int i = 0; i + 1 < (int)f.size(); i++) {
    //         cout << compare(f[i], f[i + 1]);
    //     }
    //     cout << endl;
    //     cerr << "-----\n\n";
    // };

    for (const auto &[coord, e] : events) {
        // dump();

        X = coord - 1;
        for (const auto &event : e) {
            if (event.type == EventType::Delete) {
                bool erased = open.erase(event.seg);
                assert(erased);
            }
        }

        X = coord + 1;
        for (const auto &event : e) {
            if (event.type == EventType::Insert) {
                bool inserted = open.insert(event.seg).second;
                assert(inserted);
            }
        }

        // dump();

        for (const auto &event : e) {
            auto it = open.lower_bound(event.seg);

            for (int _ : {0, 1, 2}) {
                if (it != open.end() && next(it) != open.end()) {
                    auto sa = *it;
                    auto sb = *next(it);

                    if (sa.poly_id != sb.poly_id) {
                        if (strictly_intersects(sa, sb)) {
                            // cerr << "reason: strictly_intersects" << endl;
                            return {sa.poly_id, sb.poly_id};
                        }
                        if (sa.direction == SegmentDirection::Left &&
                            sb.direction == SegmentDirection::Left) {
                            // cerr << "reason: both are left" << endl;
                            return {sa.poly_id, sb.poly_id};
                        }

                        if (a[sb.poly_id].check_point_stricktly_inside(sa.from)) {
                            // cerr << "reason: check_point_stricktly_inside" << endl;
                            return {sa.poly_id, sb.poly_id};
                        }
                    }
                }

                if (it == open.begin()) {
                    break;
                }
                it--;
            }
        }
    }

    return {-1, -1};
}

// return (-1, -1) if no intersection found
pair<int, int> find_intersections(vector<ConvexPolygon> a) {
    for (auto &p : a) {
        for (auto &pt : p.p) {
            pt.x *= 2;
            pt.y *= 2;
        }
    }

    for (int _ : {0, 1, 2}) {
        auto res = find_intersections_with_fixed_direction(a);
        if (res.first != -1) {
            return res;
        }
        for (auto &p : a) {
            p.rotate45();
        }
    }
    return {-1, -1};
}
