#pragma once
#include "testlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <typename T>
struct vect {
    T x = 0;
    T y = 0;

    vect() = default;
    vect(T x_, T y_) : x(x_), y(y_) {}

    inline T len2() const {
        return x * x + y * y;
    }

    inline vect rotate() const {
        return vect(-y, x);
    }
};

template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
    return in >> v.x >> v.y;
}

template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
    return out << "[" << v.x << "," << v.y << "]";
}

template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
    return vect(a.x + b.x, a.y + b.y);
}

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

template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
    return vect(a.x * k, a.y * k);
}

template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
    return a.x * b.x + a.y * b.y;
}

template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
    return a.x * b.y - a.y * b.x;
}

vector<vect<ll>> convex_hull(vector<vect<ll>> v) {
    int best = 0;
    for (int i = 1; i < (int)v.size(); i++) {
        if (make_pair(v[i].y, v[i].x) < make_pair(v[best].y, v[best].x)) {
            best = i;
        }
    }
    swap(v[0], v[best]);
    sort(v.begin() + 1, v.end(), [&](const auto& v1, const auto& v2) {
        auto prod = (v1 - v[0]) ^ (v2 - v[0]);
        if (prod != 0) {
            return prod > 0;
        }
        return (v1 - v[0]) * (v1 - v[0]) < (v2 - v[0]) * (v2 - v[0]);
    });
    vector<vect<ll>> st;
    st.emplace_back(v[0]);
    for (int i = 1; i < (int)v.size(); i++) {
        while (st.size() > 1) {
            auto prod = (st[(int)st.size() - 1] - st[(int)st.size() - 2]) ^ (v[i] - st[(int)st.size() - 1]);
            if (prod > 0) {
                break;
            }
            st.pop_back();
        }
        st.emplace_back(v[i]);
    }
    return st;
}

bool check_points(vector<vect<ll>> v) {
    sort(v.begin(), v.end(), [&](const auto& v1, const auto& v2) {
        return make_pair(v1.y, v1.x) < make_pair(v2.y, v2.x);
    });
    for (int i = 0; i < (int)v.size() - 1; i++) {
        if (v[i].x == v[i + 1].x && v[i].y == v[i + 1].y) {
            return false;
        }
    }
    for (int i = 0; i < (int)v.size() - 2; i++) {
        vector<int> idx((int)v.size() - i - 1);
        iota(idx.begin(), idx.end(), i + 1);
        sort(idx.begin(), idx.end(), [&](int p1, int p2) {
            return ((v[p1] - v[i]) ^ (v[p2] - v[i])) > 0;
        });
        for (int loc = 0; loc + 1 < (int)idx.size(); loc++) {
            int p1 = idx[loc];
            int p2 = idx[loc + 1];
            if (((v[p1] - v[i]) ^ (v[p2] - v[i])) == 0) {
                return false;
            }
        }
    }
    return true;
}

vect<ll> random_point(int L, int R) {
    return vect<ll>(rnd.next(L, R), rnd.next(L, R));
}

// ___________________________________________________________________________
vector<int> rand_set(int n, int k) {
    vector<int> ans;
    for (int i = 0; i < k; i++) {
        ans.push_back(rnd.next(n - k + 1));
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < k; i++) {
        ans[i] += i;
    }
    return ans;
}

vector<int> divide(int n, int k) {
    if (k == 0) return {};
    if (k == 1) return {n};
    vector<int> pos = rand_set(n - 1, k - 1);
    vector<int> len;
    len.push_back(pos[0] + 1);
    for (int i = 0; i < k - 2; i++) {
        len.push_back(pos[i + 1] - pos[i]);
    }
    len.push_back(n - pos.back() - 1);
    return len;
}

vector<int> gen_vector(int n, int x) {
    int l = rnd.next(1, n - 1);
    int r = n - l;
    vector<int> f1 = divide(x + l, l);
    for (int &t : f1) {
        t--;
    }
    vector<int> f2 = divide(x + r, r);
    for (int &t : f2) {
        t--;
    }
    for (int t : f1) {
        f2.push_back(-t);
    }
    shuffle(f2.begin(), f2.end());
    return f2;
}

ll prod(pair<int, int> a, pair<int, int> b) {
    return (ll)a.first * (ll)b.second - (ll)a.second * (ll)b.first;
}

ll scal(pair<int, int> a, pair<int, int> b) {
    return (ll)a.first * (ll)b.first + (ll)a.second * (ll)b.second;
}

bool locate(pair<int, int> v) {
    if (v.second != 0) {
        return (v.second > 0);
    }
    return (v.first > 0);
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    bool fa = locate(a);
    bool fb = locate(b);
    if (fa ^ fb) {
        return fa;
    }
    ll pr = prod(a, b);
    if (pr != 0) {
        return (pr > 0);
    }
    return scal(a, a) < scal(b, b);
}

vector<pair<int, int>> gen_polygon(int n, int xm) {
    vector<int> x, y;
    while (true) {
        x = gen_vector(n, 2 * xm);
        y = gen_vector(n, 2 * xm);
        vector<pair<int, int> > v;
        bool ch = true;
        for (int i = 0; i < n; i++) {
            if (x[i] == 0 && y[i] == 0) {
                ch = false;
                break;
            }
            int g = gcd((int)abs(x[i]), (int)abs(y[i]));
            int nx = x[i] / g;
            int ny = y[i] / g;
            if (ny < 0 || (ny == 0 && nx < 0)) {
                nx = -nx;
                ny = -ny;
            }
            v.push_back(make_pair(nx, ny));
        }
        sort(v.begin(), v.end());
        if (unique(v.begin(), v.end()) - v.begin() != n) {
            ch = false;
        }
        if (ch) {
            break;
        }
    }
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        v.push_back(make_pair(x[i], y[i]));
    }
    sort(v.begin(), v.end(), cmp);
    vector<pair<int, int> > ans;
    pair<int, int> s = make_pair(0, 0);
    for (int i = 0; i < n; i++) {
        ans.push_back(s);
        s.first += v[i].first;
        s.second += v[i].second;
    }
    int mn = xm;
    int mx = -xm;
    for (int i = 0; i < n; i++) {
        mn = min(mn, ans[i].first);
        mx = max(mx, ans[i].first);
    }
    int vx = rnd.next(-xm - mn, xm - mx);
    mn = xm;
    mx = -xm;
    for (int i = 0; i < n; i++) {
        mn = min(mn, ans[i].second);
        mx = max(mx, ans[i].second);
    }
    int vy = rnd.next(-xm - mn, xm - mx);
    for (pair<int, int> &t : ans) {
        t.first += vx, t.second += vy;
    }
    return ans;
}

vector<vect<ll>> random_polygon(int n, int x) {
    if (n == 1) {
        return {vect<ll>(rnd.next(-x, x), rnd.next(-x, x))};
    }
    if (n == 2) {
        vect<ll> v1(0, 0);
        vect<ll> v2(0, 0);
        while (v1.x == v2.x && v1.y == v2.y) {
            v1 = vect<ll>(rnd.next(-x, x), rnd.next(-x, x));
            v2 = vect<ll>(rnd.next(-x, x), rnd.next(-x, x));
        }
        return {v1, v2};
    }
    auto res = gen_polygon(n, x);
    vector<vect<ll>> ans;
    for (const auto& t : res) {
        ans.emplace_back(t.first, t.second);
    }
    if (rnd.next(2)) {
        for (int i = 0; i < (int)ans.size(); i++) {
            ans[i].x = -ans[i].x;
        }
    }
    if (rnd.next(2)) {
        for (int i = 0; i < (int)ans.size(); i++) {
            ans[i].y = -ans[i].y;
        }
    }
    if (rnd.next(2)) {
        for (int i = 0; i < (int)ans.size(); i++) {
            swap(ans[i].x, ans[i].y);
        }
    }
    ll sum = 0;
    for (int i = 0; i < (int)ans.size(); i++) {
        sum += ans[i] ^ ans[(i + 1) % (int)ans.size()];
    }
    if (sum < 0) {
        reverse(ans.begin(), ans.end());
    }
    return ans;
}
// ___________________________________________________________________________