#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}

const int INFi = 1e9;
const ll INF = 2e18;
const int LG = 20;


bool Equal(ll A, ll B) {
    return A == B;
}

bool Less(ll A, ll B) {
    return A < B;
}

bool Greater(ll A, ll B) {
    return A > B;
}

bool LessOrEqual(ll A, ll B) {
    return A <= B;
}

bool GreaterOrEqual(ll A, ll B) {
    return A >= B;
}

const ld EPS = 1e-9;

bool Equal(ld A, ld B) {
    return abs(A - B) < EPS;
}

bool Less(ld A, ld B) {
    return A + EPS < B;
}

bool Greater(ld A, ld B) {
    return A > B + EPS;
}

bool LessOrEqual(ld A, ld B) {
    return A <= B + EPS;
}

bool GreaterOrEqual(ld A, ld B) {
    return A + EPS >= B;
}

template<typename T, typename Q>
bool LessOrEqual(T A, Q B) {
    using C = std::common_type_t<T, Q>;
    return LessOrEqual(static_cast<C>(A), static_cast<C>(B));
}

template<typename T, typename Q>
bool Equal(T A, Q B) {
    using C = std::common_type_t<T, Q>;
    return Equal(static_cast<C>(A), static_cast<C>(B));
}

template<typename T, typename Q>
bool Less(T A, Q B) {
    using C = std::common_type_t<T, Q>;
    return Less(static_cast<C>(A), static_cast<C>(B));
}

template<typename T, typename Q>
bool Greater(T A, Q B) {
    using C = std::common_type_t<T, Q>;
    return Greater(static_cast<C>(A), static_cast<C>(B));
}

template<typename T, typename Q>
bool GreaterOrEqual(T A, Q B) {
    using C = std::common_type_t<T, Q>;
    return GreaterOrEqual(static_cast<C>(A), static_cast<C>(B));
}

template<typename T>
ll sgn(T x) {
    if (Equal(x, 0)) return 0;
    return Less(x, 0) ? -1 : 1;
}


template<typename T>
struct Point {
    T x;
    T y;

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

    template<typename Q>
    Point(const Point<Q> &other) {
        x = static_cast<T>(other.x);
        y = static_cast<T>(other.y);
    }


    template<typename Q>
    Point(Point<Q> &&other) {
        x = static_cast<T>(other.x);
        y = static_cast<T>(other.y);
    }

    template<typename Q>
    Point<std::common_type_t<T, Q>> operator+(const Point<Q> &oth) const {
        return Point{x + oth.x, y + oth.y};
    }

    template<typename Q>
    Point<std::common_type_t<T, Q>> operator-(const Point<Q> &oth) const {
        return {x - oth.x, y - oth.y};
    }

    template<typename Q>
    bool operator==(const Point<Q> &oth) const {
        return x == oth.x && y == oth.y;
    }

    template<typename Q>
    bool operator<(const Point<Q> &oth) const {
        return make_pair(x, y) < make_pair(oth.x, oth.y);
    }

    template<typename Q>
    requires (is_integral_v<Q> || is_floating_point_v<Q>)
    Point<std::common_type_t<Q, T>> operator*(const Q &b) const {
        return {x * b, y * b};
    }


    template<typename Q>
    requires (is_integral_v<Q> || is_floating_point_v<Q>)
    Point<ld> operator/(const Q &b) const {
        return {(ld) x / b, (ld) y / b};
    }

    template<typename Q>
    std::common_type_t<Q, T> operator*(const Point<Q> &oth) const {
        return x * oth.y - y * oth.x;
    }

    template<typename Q>
    std::common_type_t<Q, T> operator%(const Point<Q> &oth) const {
        return x * oth.x + y * oth.y;
    }

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

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

    friend ostream &operator<<(ostream &stream, const Point &P) {
        stream << P.x << ' ' << P.y;
        return stream;
    }


    friend istream &operator>>(istream &stream, Point &P) {
        stream >> P.x >> P.y;
        return stream;
    }
};

template<typename T>
Point<T> rotateCW(const Point<T> &P) {
    return {P.y, -P.x};
}

template<typename T>
Point<T> rotateCCW(const Point<T> &P) {
    return {-P.y, P.x};
}

template<typename T, typename Q>
bool Equal(const Point<T> &a, const Point<Q> &b) {
    return Equal(a.x, b.x) && Equal(a.y, b.y);
}

template<typename T, typename Q>
bool Less(const Point<T> &a, const Point<Q> &b) {
    if (!Equal(a.x, b.x)) return Less(a.y, b.y);
    return Less(a.y, b.y);
}

template<typename T, typename Q>
bool Greater(const Point<T> &a, const Point<Q> &b) {
    if (!Equal(a.x, b.x)) return Greater(a.y, b.y);
    return Greater(a.y, b.y);
}

template<typename T>
Point<T> operator-(const Point<T> &a) {
    return {-a.x, -a.y};
}


template<typename T>
T len2(const Point<T> &a) {
    return a % a;
}

template<typename T>
ld len(const Point<T> &a) {
    return sqrtl(len2(a));
}

template<typename T, typename Q>
T dist2(const Point<T> &a, const Point<Q> &b) {
    return len2(a - b);
}

template<typename T, typename Q>
ld dist(const Point<T> &a, const Point<Q> &b) {
    return len(a - b);
}

using pt = Point<ll>;
using ptd = Point<ld>;

template<typename T = ld>
const Point<T> NULL_POINT = {T(-INFi - 1337), T(INFi + 228)};

template<typename T>
struct Segment;

template<typename T>
struct Ray;

template<typename T>
struct Line {
    T a, b, c;
    // ax + by = c


    template<class Q>
    Line(const Line<Q> &other) {
        a = other.a;
        b = other.b;
        c = other.c;
    }

    Line(const Point<T> &F, Point<T> V, bool isDirection = false) {
        if (!isDirection) {
            V -= F;
        }
        a = V.y;
        b = -V.x;
        c = a * F.x + b * F.y;
    }


    Line(const T &a1 = 0, const T &b1 = 0, const T &c1 = 0) {
        a = a1;
        b = b1;
        c = c1;
    }

    template<class Q>
    explicit Line(const Segment<Q> &other) : Line(other.A, other.B, false) {
    }

    template<class Q>
    explicit Line(const Ray<Q> &other) : Line(other.A, other.V, true) {
    }

    pair<ptd, ptd> GetPointAndDirection() const {
        ptd V = {-b, a};
        ptd A;
        if (!Equal(a, 0)) {
            A.y = 0;
            A.x = c / (ld) a;
        } else if (!Equal(b, 0)) {
            A.x = 0;
            A.y = c / (ld) b;
        } else {
            assert(0);
        }
        return {A, V};
    }

    template<class Q>
    ptd Proj(const Point<Q> &P) const {
        auto [A, V] = GetPointAndDirection();
        ld value = (P - A) % V;
        value /= (ld) len2(V);
        return ptd(A) + (ptd(V) * value);
    }

    template<class Q>
    bool Contains(const Point<Q> &P) const {
        return Equal(GetValue(P), c);
    }

    template<typename Q>
    ld Dist(const Point<Q> &P) const {
        return dist(Proj(P), P);
    }

    template<typename Q>
    std::common_type_t<Q, T> GetValue(const Point<Q> &P) const {
        return a * P.x + b * P.y;
    }

    friend ostream &operator<<(ostream &stream, const Line &L) {
        stream << L.a << ' ' << L.b << ' ' << L.c;
        return stream;
    }


    friend istream &operator>>(istream &stream, Line &L) {
        stream >> L.a >> L.b >> L.c;
        return stream;
    }
};


template<typename Q, typename U>
ld Dist(const Point<Q> &A, const Line<U> &line) {
    return line.Dist(A);
}

template<typename Q, typename U>
Point<ld> Intersect(const Line<Q> &line1, const Line<U> &line2) {
    using C = std::common_type_t<Q, U>;
    C det = line1.a * line2.b - line1.b * line2.a;
    if (Equal(det, 0)) return NULL_POINT<ld>;
    C detx = line1.c * line2.b - line1.b * line2.c;
    C dety = line1.a * line2.c - line1.c * line2.a;
    return {(ld) detx / (ld) det, (ld) dety / (ld) det};
}

template<typename Q, typename U>
bool IsParallel(const Line<Q> &line1, const Line<U> &line2) {
    return Equal(line1.a * line2.b - line1.b * line2.a, 0);
}

template<typename Q, typename U>
ld Dist(const Line<Q> &line1, const Line<U> &line2) {
    if (IsParallel(line1, line2)) {
        return line1.Dist(line2.A);
    }
    return 0;
}


template<typename T, typename U, typename V>
bool IsCollinear(const Point<T> &a, const Point<U> &b, const Point<V> &c) {
    return Equal((c - a) * (b - a), 0);
}

template<typename T, typename U, typename V>
bool IsInside(T L, U R, V P) {
    return LessOrEqual(L, P) && LessOrEqual(P, R);
}

template<typename T>
struct Segment {
    Point<T> A, B;

    Segment(const Point<T> &a = {0, 0}, const Point<T> &b = {0, 0}) : A(a), B(b) {
    }


    template<class Q>
    Segment(const Segment<Q> &other) : A(other.A), B(other.B) {
    }

    T len2() const {
        return dist2(A, B);
    }

    ld len() const {
        return dist(A, B);
    }

    template<class Q>
    bool Contains(const Point<Q> &P) const {
        if (!IsCollinear(A, B, P)) {
            return false;
        }
        return IsInside(min(A.x, B.x), max(A.x, B.x), P.x) && IsInside(min(A.y, B.y), max(A.y, B.y), P.y);
    }

    template<typename Q>
    ld Dist(const Point<Q> &P) const {
        ld answer = min(dist(P, A), dist(P, B));
        ptd Ap = Line<ld>(*this).Proj(P);
        if (Contains(Ap)) {
            answer = dist(Ap, P);
        }
        return answer;
    }
};


template<typename Q, typename U>
ld Dist(const Point<Q> A, const Segment<U> &seg) {
    return seg.Dist(A);
}


template<typename U, typename V>
bool isIntersected(const Segment<U> &seg1, const Segment<V> &seg2) {
    ll s1 = sgn((seg1.B - seg1.A) * (seg2.A - seg1.A)) * sgn((seg1.B - seg1.A) * (seg2.B - seg1.A));
    if (s1 > 0) return false;
    ll s2 = sgn((seg2.B - seg2.A) * (seg1.A - seg2.A)) * sgn((seg2.B - seg2.A) * (seg1.B - seg2.A));
    if (s2 > 0) return false;
    return s1 < 0 || s2 < 0 || seg1.Contains(seg2.A) || seg1.Contains(seg2.B) || seg2.Contains(seg1.A);
}

template<typename U, typename V>
ld Dist(const Segment<U> &seg1, const Segment<V> &seg2) {
    if (isIntersected(seg1, seg2)) {
        return 0;
    }
    return min(min(seg1.Dist(seg2.A), seg1.Dist(seg2.B)), min(seg2.Dist(seg1.A), seg2.Dist(seg1.B)));
}

template<typename U, typename V>
bool isIntersected(const Segment<U> &seg, const Line<V> &line) {
    return sgn((seg.A - line.A) * line.V) * sgn((seg.B - line.A) * line.V) <= 0;
}

template<typename Q, typename U>
ld Dist(const Segment<Q> &seg, const Line<U> &line) {
    if (isIntersected(seg, line)) {
        return 0;
    }
    return min(line.Dist(seg.A), line.Dist(seg.B));
}

template<typename T>
struct Ray {
    Point<T> A, V;

    Ray(const Point<T> &a = {0, 0}, const Point<T> &v = {1, 0}, bool isDirection = false) {
        if (isDirection) {
            A = a;
            V = v;
        } else {
            A = a;
            V = v - a;
        }
    }

    template<class Q>
    Ray(const Ray<Q> &other) : A(other.A), V(other.V) {
    }

    template<class Q>
    Ray(const Segment<Q> &other) : A(other.A), V(other.B - other.A) {
    }

    template<class Q>
    bool Contains(const Point<Q> &P) const {
        return Equal(V * (P - A), 0) && GreaterOrEqual(V % (P - A), 0);
    }

    template<typename Q>
    ld Dist(const Point<Q> &P) const {
        ld answer = dist(P, A);
        ptd Ap = Line<ld>(*this).Proj(P);
        if (Contains(Ap)) {
            answer = dist(Ap, P);
        }
        return answer;
    }
};


template<typename Q, typename U>
ld Dist(const Point<Q> A, const Ray<U> &ray) {
    return ray.Dist(A);
}


template<typename U, typename V>
bool isIntersected(const Segment<U> &seg, const Ray<V> &ray) {
    ll sA = sgn((seg.A - ray.A) * ray.V);
    ll sB = sgn((seg.B - ray.A) * ray.V);
    if (sA * sB > 0) return false;
    if (sA == 0 || sB == 0) return ray.Contains(seg.A) || ray.Contains(seg.B);
    ll sAB = sgn((seg.A - ray.A) * (seg.B - ray.A));
    return sAB == 0 || sAB == sA;
}


template<typename U, typename V>
ld Dist(const Segment<U> &seg, const Ray<V> &ray) {
    if (isIntersected(seg, ray)) {
        return 0;
    }
    return min(min(ray.Dist(seg.A), ray.Dist(seg.B)), seg.Dist(ray.A));
}


template<typename U, typename V>
bool isIntersected(const Ray<U> &ray1, const Ray<V> &ray2) {
    auto mid = Intersect(Line<U>(ray1), Line<V>(ray2));
    if (ray1.Contains(mid) && ray2.Contains(mid)) return true;
    return ray1.Contains(ray2.A) || ray2.Contains(ray1.A);
}

template<typename U, typename V>
ld Dist(const Ray<U> &ray1, const Ray<V> &ray2) {
    if (isIntersected(ray1, ray2)) {
        return 0;
    }
    return min(ray1.Dist(ray2.A), ray2.Dist(ray1.A));
}

template<typename U, typename V>
bool isIntersected(const Ray<U> &ray, const Line<V> &line) {
    auto mid = Intersect(Line<U>(ray), line);
    if (ray.Contains(mid)) return true;
    return line.Contains(ray.A);
}

template<typename U, typename V>
ld Dist(const Ray<U> &ray, const Line<V> &line) {
    if (isIntersected(ray, line)) {
        return 0;
    }
    return line.Dist(ray.A);
}

const ld PI = atan2(0, -1);

template<typename T = ld>
struct Circle {
    Point<T> O;
    T R;

    Circle(const Point<T> &o = {0, 0}, const T &r = 0) : O(o), R(r) {}

    template<typename Q>
    Circle(const Circle<Q> &other) : O(other.O), R(other.R) {}

    template<typename Q>
    Circle(Circle<Q> &&other) : O(other.O), R(other.R) {}

    ld Area() const {
        return R * R * PI;
    }


    template<typename U, typename V>
    Point<ld> GetCircleCenterWithZero(const Point<U> &b,
                                      const Point<V> &c) {
        ld B = len2(b);
        ld C = len2(c);
        ld D = b * c;
        return {(c.y * B - b.y * C) / (2 * D),
                (b.x * C - c.x * B) / (2 * D)};
    }

    template<typename U, typename V, typename W>
    Circle(const Point<U> &A, const Point<V> &B,
           const Point<W> &C) {
        static_assert(std::is_same_v<T, ld>);
        O = GetCircleCenterWithZero(B - A, C - A);
        R = len(O);
        O += A;
    }

    template<typename U, typename V>
    Circle(const Point<U> &A, const Point<V> &B) {
        static_assert(std::is_same_v<T, ld>);
        O = (A + B) / (ld) 2;
        R = (ld) dist(A, B) / (ld) 2;
    }

    template<typename U>
    bool isInside(const Point<U> &P) const {
        return LessOrEqual(dist(P, O), R);
    }
};

// return (L, R) points in counter-clock-wise order related circle1
// if no intersect or coincide return (NULL_POINT, NULL_POINT)
template<typename T, typename U>
pair<Point<ld>, Point<ld>> Intersect(const Circle<T> &circle1, const Circle<U> &circle2) {
    if (Equal(circle1.O, circle2.O) && Equal(circle2.R, circle1.R)) return {NULL_POINT<ld>, NULL_POINT<ld>};
    auto d2 = dist2(circle2.O, circle1.O);
    if (Equal(d2, 0)) return {NULL_POINT<ld>, NULL_POINT<ld>};
    if (Less((circle1.R + circle2.R) * (circle2.R + circle1.R), d2) ||
        Less(d2, (circle1.R - circle2.R) * (circle1.R - circle2.R)))
        return {NULL_POINT<ld>, NULL_POINT<ld>};
    ld d = sqrtl(d2);
    ld A = (d2 - circle2.R * circle2.R + circle1.R * circle1.R) / (2 * d);
    ld B = sqrtl(max((ld) 0, circle1.R * circle1.R - A * A));
    Point<ld> V = (circle2.O - circle1.O) / d;
    Point<ld> M = circle1.O + V * A;
    V = rotateCCW(V) * B;
    return {M - V, M + V};
}

template<typename T, typename U>
pair<Point<ld>, Point<ld>> Intersect(const Circle<T> &circle, const Line<U> &line) {
    auto [a, b] = line.GetPointAndDirection();
    a -= circle.O;
    auto A = len2(b);
    auto B = a % b;
    auto C = len2(a) - circle.R * circle.R;
    auto D = B * B - A * C;
    if (Less(D, 0)) return {NULL_POINT<ld>, NULL_POINT<ld>};
    if (D < 0) D = 0;
    Point<ld> result = circle.O + a;
    return {result + b * (-B + sqrtl(D)) / (ld) A,
            result + b * (-B - sqrtl(D)) / (ld) A};
}

template<typename U, typename V>
ld IntersectionArea(const Circle<U> &circle1, const Circle<V> &circle2) {
    ld d = dist(circle1.O, circle2.O);
    if (GreaterOrEqual(d, circle1.R + circle2.R)) {
        return 0;
    }
    if (LessOrEqual(d + circle1.R, circle2.R)) {
        return circle1.Area();
    }
    if (LessOrEqual(d + circle2.R, circle1.R)) {
        return circle2.Area();
    }
    ld alpha = acos((circle1.R * circle1.R + d * d - circle2.R * circle2.R) / (2 * circle1.R * d)) * 2;
    ld beta = acos((circle2.R * circle2.R + d * d - circle1.R * circle1.R) / (2 * circle2.R * d)) * 2;
    return 0.5 * circle2.R * circle2.R * (beta - sin(beta)) +
           0.5 * circle1.R * circle1.R * (alpha - sin(alpha));
}


template<typename U, typename V>
ld UnionArea(const Circle<U> &circle1, const Circle<V> &circle2) {
    return circle1.Area() + circle2.Area() - IntersectionArea(circle1, circle2);
}

mt19937 rng(123212);

template<typename T, typename U>
bool IsContainsPoints(const Circle<T> &c, const vector<Point<U>> &pts) {
    for (auto &p: pts) {
        if (!c.isInside(p)) {
            return false;
        }
    }
    return true;
}

template<typename T>
Circle<ld> MinCircle(vector<Point<T>> &pts) {
    int n = pts.size();
    Circle<ld> C(pts[0], (ld) 0);
    for (int i = 1; i < n; i++) {
        if (!C.isInside(pts[i])) {
            C = Circle<ld>(pts[i], (ld) 0);
            for (int j = 0; j < i; j++) {
                if (!C.isInside(pts[j])) {
                    C = Circle<ld>(pts[i], pts[j]);
                    for (int k = 0; k < j; k++) {
                        if (!C.isInside(pts[k])) {
                            C = Circle<ld>(pts[i], pts[j], pts[k]);
                        }
                    }
                }
            }
        }
    }
    return C;
}


template<typename T>
vector<Point<T>> ConvexHull(vector<Point<T>> pts) {
    int min_idx = min_element(all(pts)) - pts.begin();
    swap(pts[0], pts[min_idx]);

    sort(pts.begin() + 1, pts.end(), [&](const Point<T> &a, const Point<T> &b) {
        auto val = (a - pts[0]) * (b - pts[0]);
        if (val != 0) return val > 0;
        return dist2(a, pts[0]) < dist2(b, pts[0]);
    });
    vector<Point<T>> convex_hull = {pts[0]};
    int sz = 0;
    for (int i = 1; i < (int) pts.size(); ++i) {
        while (sz && LessOrEqual((convex_hull[sz] - convex_hull[sz - 1]) * (pts[i] - convex_hull[sz]), 0)) {
            convex_hull.pop_back();
            --sz;
        }
        convex_hull.push_back(pts[i]);
        ++sz;
    }
    return convex_hull;
}

template<typename T, typename U>
bool VComp(const Point<T> &a, const Point<U> &b) {
    bool upA = a.y > 0 || (a.y == 0 && a.x >= 0);
    bool upB = b.y > 0 || (b.y == 0 && b.x >= 0);
    if (upA != upB) return upA;
    auto val = a * b;
    if (val != 0) return val > 0;
    return len2(a) < len2(b);
}

template<typename T, typename U>
bool VCompNoLen(const Point<T> &a, const Point<U> &b) {
    bool upA = a.y > 0 || (a.y == 0 && a.x >= 0);
    bool upB = b.y > 0 || (b.y == 0 && b.x >= 0);
    if (upA != upB) return upA;
    auto val = a * b;
    return val > 0;
}

template<typename T>
T SignedArea(vector<Point<T>> &pts) {
    int n = pts.size();
    T res = 0;
    rep(i, n) {
        res += pts[i] * pts[(i + 1) % n];
    }
    return res;
}

template<typename T>
T Area(vector<Point<T>> &pts) {
    return abs(SignedArea(pts));
}


template<typename T>
void NormalizeConvexPoly(vector<Point<T>> &A) {
    if (SignedArea(A) < 0) {
        reverse(all(A));
    }
    int min_idx = min_element(all(A), [&](const Point<T> &a, const Point<T> &b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    }) - A.begin();
    rotate(A.begin(), A.begin() + min_idx, A.end());
}

template<typename T>
vector<Point<T>> MinkowskiSum(vector<Point<T>> A, vector<Point<T>> B) {
    NormalizeConvexPoly(A);
    NormalizeConvexPoly(B);
    if (A.empty()) return B;
    if (B.empty()) return A;
    Point<T> S = A[0] + B[0];
    vector<Point<T>> edges;
    int n = A.size(), m = B.size();
    rep(i, n) edges.push_back(A[(i + 1) % n] - A[i]);
    rep(i, m) edges.push_back(B[(i + 1) % m] - B[i]);
    sort(all(edges), VComp<T, T>);
    rotate(edges.begin(), edges.end() - 1, edges.end());
    edges[0] = S;
    for (int i = 1; i < edges.size(); ++i) {
        edges[i] += edges[i - 1];
    }
    return edges;
}

template<typename T>
ld DistConvexPolygons(const vector<Point<T>> &A, vector<Point<T>> B) {
    for (auto &p: B) p = -p;
    auto C = MinkowskiSum(A, B);
    NormalizeConvexPoly(C);
    int n = C.size();
    bool ok = true;
    rep(i, n) ok &= ((C[i] * C[(i + 1) % n]) >= 0);
    if (ok) return 0;
    Point<T> mid(0, 0);
    ld d = dist(mid, C[0]);
    rep(i, n) d = min(d, Dist(mid, Segment(C[(i + 1) % n], C[i])));
    return d;
}


template<typename T, typename U>
pair<int, int> GetTangents(const vector<Point<T>> &poly, const Line<U> &line) {
    int n = poly.size();
    auto start = line.GetValue(poly[0]);
    bool isUp = line.GetValue(poly[1]) >= start;
    pair<int, int> result = {-1, -1};
    if (isUp) {
        result.first = FindLastFalse(0, n, [&](const int &i) {
            if (!i) return false;
            auto val = line.GetValue(poly[i]);
            if (val < start) return true;
            auto valp = line.GetValue(poly[i - 1]);
            if (valp > val) return true;
            return false;
        });
        result.second = FindLastFalse(0, n, [&](const int &i) {
            if (i <= 1) return false;
            auto val = line.GetValue(poly[i]);
            if (val >= start) return false;
            auto valp = line.GetValue(poly[i - 1]);
            if (valp < val) return true;
            return false;
        });
    } else {
        result.first = FindLastFalse(0, n, [&](const int &i) {
            if (i <= 1) return false;
            auto val = line.GetValue(poly[i]);
            if (val <= start) return false;
            auto valp = line.GetValue(poly[i - 1]);
            if (valp > val) return true;
            return false;
        });
        result.second = FindLastFalse(0, n, [&](const int &i) {
            if (!i) return false;
            auto val = line.GetValue(poly[i]);
            if (val > start) return true;
            auto valp = line.GetValue(poly[i - 1]);
            if (valp < val) return true;
            return false;
        });
    }
    for (int i: {0, 1, n - 2, n - 1}) {
        if (i < 0 || i >= (int) poly.size()) continue;
        if (line.GetValue(poly[result.first]) < line.GetValue(poly[i])) result.first = i;
        if (line.GetValue(poly[result.second]) > line.GetValue(poly[i])) result.second = i;
    }
    return result;
}

template<typename T, typename U>
pair<int, int> GetTangents(const vector<Point<T>> &poly, const Point<U> &P) {
    int n = poly.size();
    auto GetDirection = [&](int i, int j) {
        if (i < 0) i += n;
        if (j < 0) j += n;
        if (i >= n) i -= n;
        if (j >= n) j -= n;
        if (i == j) return 0;
        auto val = (poly[i] - P) * (poly[j] - P);
        if (val > 0) return -2;
        if (val < 0) return 2;
        auto q = dist2(poly[i], P) - dist2(poly[j], P);
        if (q > 0) return -1;
        if (q < 0) return 1;
        assert(false);
        return 0;
    };
    ll d01 = GetDirection(0, 1);
    pair<int, int> result = {-1, -1};
    if (d01 == -1) {
        result.first = 0;
    } else if (d01 == -2) {
        result.first = FindFirstTrue(0, n, [&](const int &i) {
            if (!i) return false;
            if (GetDirection(0, i) >= -1) return true;
            if (GetDirection(i, i + 1) == -2) return false;
            return true;
        }) % n;
    } else {
        assert(d01 == 1 || d01 == 2);
        result.first = FindFirstTrue(0, n, [&](const int &i) {
            ll v = GetDirection(0, i);
            assert(v != -1);
            if (v >= 2) return false;
            if (GetDirection(i, i + 1) == -2) return false;
            return true;
        }) % n;
    }
    assert(GetDirection(result.first, result.first + 1) >= -1 && GetDirection(result.first, result.first - 1) >= -1);
    if (d01 == 1) {
        result.second = 1;
    } else if (d01 == 2) {
        result.second = FindFirstTrue(0, n, [&](const int &i) {
            if (!i) return false;
            if (GetDirection(0, i) <= 1) return true;
            if (GetDirection(i, i + 1) >= 1) return false;
            return true;
        }) % n;
    } else {
        assert(d01 == -1 || d01 == -2);
        result.second = FindFirstTrue(0, n, [&](const int &i) {
            if (!i) return false;
            ll v = GetDirection(0, i);
            assert(v != 1);
            if (v <= -2) return false;
            if (GetDirection(i, i + 1) >= 1) return false;
            return true;
        }) % n;
    }
    assert(GetDirection(result.second, result.second + 1) <= 1 && GetDirection(result.second, result.second - 1) <= 1);
    return result;
}

pt min_ang(const pt &a, const pt &b) {
    return VComp(a, b) ? a : b;
}


pt FindNext(const pt &a, const pt &b) {
    if (a * b == 0 || VComp(b, a)) return {-1, 1};
    return rotateCW(b - a);
}

struct SegTree {
    struct Node {
        pt best;
        pt melt;
        pt upd;

        Node() : best({0, 0}), melt({-1, 1}), upd({0, 0}) {}
    };

    pt T;

    int n;
    vector<Node> t;

    void apply(int v, pt x) {
        t[v].best += x;
        t[v].upd += x;
    }

    bool IsBetter(const pt &a, const pt &b) {
        ll vA = a % T;
        ll vB = b % T;
        if (vA != vB) return vA > vB;
        return VComp(b, a);
    }

    void pull(int v) {
        pt A = t[v << 1].best;
        pt B = t[v << 1 | 1].best;
        t[v].melt = min_ang(t[v << 1].melt, t[v << 1 | 1].melt);
        if (IsBetter(B, A)) swap(A, B);
        t[v].best = A;
        t[v].melt = min_ang(t[v].melt, FindNext(A, B));
    }

    void init(vector<pt> &l) {
        n = l.size();
        T = {1, 0};
        t.resize(n * 4);
        init(1, 0, n, l);
    }

    void init(int v, int l, int r, vector<pt> &lines) {
        if (l + 1 == r) {
            t[v].best = lines[l];
            return;
        }
        init(v << 1, l, (l + r) >> 1, lines);
        init(v << 1 | 1, (l + r) >> 1, r, lines);
        pull(v);
    }

    void push(int v) {
        apply(v << 1, t[v].upd);
        apply(v << 1 | 1, t[v].upd);
        t[v].upd = {0, 0};
    }

    void propagate(int v) {
        if (VComp(T, t[v].melt)) return;
        push(v);
        propagate(v << 1);
        propagate(v << 1 | 1);
        pull(v);
    }

    void updateT(pt T2) {
        assert(T == T2 || VComp(T, T2));
        T = T2;
        propagate(1);
    }

    int FindLast(int v, int l, int r, int rq, ll value) {
        if (rq <= l) return -1;
        if (t[v].best % T < value) return -1;
        if (l + 1 == r) return l;
        push(v);
        int d = FindLast(v << 1 | 1, (l + r) >> 1, r, rq, value);
        if (d != -1) return d;
        return FindLast(v << 1, l, (l + r) >> 1, rq, value);
    }

    int FindLast(ll value, int rq) {
        return FindLast(1, 0, n, rq, value);
    }

    void upd(int v, int l, int r, int lq, int rq, pt &x) {
        if (rq <= l || r <= lq) return;
        if (lq <= l && r <= rq) {
            apply(v, x);
            propagate(v);
            return;
        }
        push(v);
        upd(v << 1, l, (l + r) >> 1, lq, rq, x);
        upd(v << 1 | 1, (l + r) >> 1, r, lq, rq, x);
        pull(v);
    }

    void upd(int lq, int rq, pt x) {
        upd(1, 0, n, lq, rq, x);
    }
};

struct Event {
    pt ang;
    int i;

    bool isQuery;
    int v;
    ll c;
    pt new_p;
};



struct fenwick {
    int n{};
    vector<ll> fenw{};

    void build(int k) {
        n = k;
        fenw.resize(n);
    }

    void upd(int i, ll x) {
        for (; i < n; i = i | (i + 1)) fenw[i] += x;
    }

    ll get(int i) {
        ll res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) res += fenw[i];
        return res;
    }

    ll get(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};

void solve() {
    int n;
    cin >> n;


    SegTree st;
    {
        vector<pt> L(n, {0, 0});
        st.init(L);
    }

    vector<Event> events;
    vector<pt> cur(n - 1, {0, 0});
    fenwick fa, fb;
    fa.build(n);
    fb.build(n);

    auto update = [&](int i, pt nw) {
        pt ve = nw - cur[i];
        st.upd(0, i + 1, nw - cur[i]);

        fa.upd(0, ve.x);
        fa.upd(i + 1, -ve.x);

        fb.upd(0, ve.y);
        fb.upd(i + 1, -ve.y);

        cur[i] = nw;
    };

    rep(i, n) {
        {
            pt L;
            cin >> L.x >> L.y;
            st.upd(i, i + 1, L);
        }
        if (i == n - 1) break;
        int m;
        cin >> m;
        vector<pt> pts(m);
        rep(j, m) cin >> pts[j].x >> pts[j].y;

        {
            pts = ConvexHull(pts);
            sort(all(pts), [&](const pt &a, const pt &b) {
                return make_pair(a.x, a.y) < make_pair(b.x, b.y);
            });
            vector<pt> pts2;
            for (auto &p: pts) {
                while (!pts2.empty() && pts2.back().y <= p.y) pts2.pop_back();
                pts2.push_back(p);
            }
            reverse(all(pts2));
            pts = pts2;
            m = pts.size();
        }

        assert(m >= 1);

        update(i, pts[0]);
        for (int j = 1; j < m; ++j) {
            Event e;
            e.isQuery = false;
            e.i = i;
            e.c = 0;
            e.v = -1;
            e.new_p = pts[j];

            e.ang = FindNext(pts[j - 1], pts[j]);

            events.push_back(e);
        }
    }

    int q;
    cin >> q;
    vector<int> ans(q, -1);
    rep(i, q) {
        Event e;
        e.i = i;
        cin >> e.v;
        e.v--;
        cin >> e.ang.x >> e.ang.y;
        cin >> e.c;
        e.new_p = {0, 0};
        e.isQuery = true;
        events.push_back(e);
    }

    sort(all(events), [&](const Event &i, const Event &j) {
        return VComp(i.ang, j.ang);
    });

    for (auto &e: events) {
        st.updateT(e.ang);
        if (e.isQuery) {
            ll have = fa.get(e.v) * e.ang.x + fb.get(e.v) * e.ang.y;
            int pos = st.FindLast(e.c + have, e.v + 1);
            ans[e.i] = pos;
        } else {
            update(e.i, e.new_p);
        }
    }

    rep(i, q) {
        if (ans[i] != -1) ans[i]++;
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}