代码

// noi17f 【NOI2017】分身术
// Every query state is P \ D_t with |D_t| <= 100 (deleted points are restored each step),
// so a deleted point strictly inside hull(P) cannot change the answer: the answer is
// area(hull(P)) unless D_t removes vertices of hull(P) =: H0.
// Answer = shoelace over the surviving arcs of H0 plus, for every maximal deleted run
// (x = v_{a-1}, y = v_{b+1}), the convex chain of alive points inside cap(x,y) (the region
// right of chord x->y).  That chain is produced by quickhull: repeatedly take the alive
// point farthest from the current chord.  "Alive support in direction d" is answered with
// the onion layers (L_1 = H0, L_2 = hull(P\L_1), ...): min over L_j of a linear function is
// non-decreasing in j, so the walk stops as soon as no deeper layer can improve.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sys/auxv.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;

struct DI { u64 abi; const char* in; u64 insz; char* out; u64 outlim; u64 outsz; char* err;
            u64 errlim; u64 errsz; const char* IB; u64 IBlim; char* OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static const int MAXN = 100005;
static const int MAXLAY = 512;

static int n, m;
static int px[MAXN], py[MAXN];
static int ordr[MAXN];
static unsigned char del_[MAXN], used_[MAXN];
static int layerOf[MAXN], idxIn[MAXN];
static int hh;
static int hp[MAXN];
static int hpos[MAXN];
static ll areaH0;
static int scratch[MAXN];

static vector<int> lay[MAXLAY + 2];
static vector<ll> pfx[MAXLAY + 2];
struct LPt { int x, y; };
static LPt lp[MAXN];                 // layer vertices inline, hull order (one cache line / 8 pts)
static int lstart[MAXLAY + 3], lsz[MAXLAY + 3];
static int lslot = 0;
static int iminIdx[MAXLAY + 2], imaxIdx[MAXLAY + 2];
static int nlay = 0;
static bool capHit = false;
static int leftPts[MAXN];
static int nleft = 0;
static bool leftDone = false;

static char *ib, *ibEnd;
// task-59 round 3: eight ASCII digits are converted in one SWAR step; the scalar loop only
// handles the tail of longer numbers and the short ones.
static inline int rd() {
    while (ib < ibEnd && (unsigned char)*ib <= ' ') ib++;
    int sgn = 1;
    if (ib < ibEnd && *ib == '-') { sgn = -1; ib++; }
    int v = 0;
    if (ib + 8 <= ibEnd) {
        u64 ch;
        memcpy(&ch, ib, 8);
        u64 lo = ch & 0x0F0F0F0F0F0F0F0Full;
        if (((ch >> 4) & 0x0F0F0F0F0F0F0F0Full) == 0x0303030303030303ull) {
            // byte i holds digit i (byte 0 = most significant); folding pairwise keeps every
            // partial value inside its own byte/word/dword lane, so no carry escapes
            u64 P = (lo * 10 + (lo >> 8)) & 0x00FF00FF00FF00FFull;
            u64 Q = (P * 100 + (P >> 16)) & 0x0000FFFF0000FFFFull;
            v = (int)((Q * 10000 + (Q >> 32)) & 0xFFFFFFFFull);
            ib += 8;
        }
    }
    while (ib < ibEnd && (unsigned char)*ib >= '0') { v = v * 10 + (*ib - '0'); ib++; }
    return v * sgn;
}

// Lemire fastmod for a 32-bit dividend with the fixed divisor n; 2^32 mod n is precomputed to
// handle negative t exactly.  Replaces a hardware 64-bit division in the per-deletion path.
static u64 g_Mn; static unsigned g_C32;
static inline unsigned fastmodN(unsigned a) {
    u64 low = (u64)g_Mn * a;
    return (unsigned)(((unsigned __int128)low * (unsigned)n) >> 64);
}
static inline unsigned idmod(ll t) {          // ((t % n) + n) % n, exact for |t| < 2^31 + n
    if (t >= 0) return fastmodN((unsigned)(u64)t);
    unsigned r = fastmodN((unsigned)(u64)t);  // (t + 2^32) mod n
    return (r >= g_C32) ? r - g_C32 : r + (unsigned)n - g_C32;
}

static inline ll cr(int a, int b, int c) {
    return (ll)(px[b] - px[a]) * (ll)(py[c] - py[a]) - (ll)(py[b] - py[a]) * (ll)(px[c] - px[a]);
}
static inline ll crossv(int a, int b) { return (ll)px[a] * py[b] - (ll)py[a] * px[b]; }
static inline int L_of(int j, int k) { int s = (int)lay[j].size(); return lay[j][((k % s) + s) % s]; }
static inline ll dotv(int id, ll dx, ll dy) { return (ll)px[id] * dx + (ll)py[id] * dy; }

// convex hull of points with used_==0, strict turns, CCW -> scratch, returns size
static int buildHull() {
    int hn = 0;
    for (int t = 0; t < n; t++) {
        int id = ordr[t];
        if (used_[id]) continue;
        while (hn >= 2 && cr(scratch[hn - 2], scratch[hn - 1], id) <= 0) hn--;
        scratch[hn++] = id;
    }
    if (hn < 2) return hn;      // 0 or 1 usable point
    int low = hn;
    int las = n - 1;
    while (used_[ordr[las]]) las--;
    for (int t = las - 1; t >= 0; t--) {
        int id = ordr[t];
        if (used_[id]) continue;
        while (hn >= low + 1 && cr(scratch[hn - 2], scratch[hn - 1], id) <= 0) hn--;
        scratch[hn++] = id;
    }
    hn--;
    return hn;
}

static void assignLayer(int j, int hn) {
    lay[j].assign(scratch, scratch + hn);
    lstart[j] = lslot; lsz[j] = hn;
    for (int i = 0; i < hn; i++) { lp[lslot + i].x = px[scratch[i]]; lp[lslot + i].y = py[scratch[i]]; }
    lslot += hn;
    {   // prefix cross sums over the doubled cycle (arc sums in O(1))
        int s = hn;
        pfx[j].assign(2 * s + 1, 0);
        for (int t = 0; t < 2 * s; t++)
            pfx[j][t + 1] = pfx[j][t] + crossv(lay[j][t % s], lay[j][(t + 1) % s]);
    }
    for (int i = 0; i < hn; i++) {
        int id = scratch[i];
        used_[id] = 1; layerOf[id] = j; idxIn[id] = i;
    }
    int imn = 0, imx = 0;
    for (int i = 1; i < hn; i++) {
        int a = scratch[i];
        if (px[a] < px[scratch[imn]] || (px[a] == px[scratch[imn]] && py[a] < py[scratch[imn]])) imn = i;
        if (px[a] > px[scratch[imx]] || (px[a] == px[scratch[imx]] && py[a] > py[scratch[imx]])) imx = i;
    }
    iminIdx[j] = imn; imaxIdx[j] = imx;
}

static bool buildNextLayer() {
    if (leftDone) return false;
    if (nlay >= MAXLAY) { capHit = true; leftDone = true; return false; }
    int hn = buildHull();
    if (hn < 3) {   // remaining points are collinear (or <=2): they live on one line
        nleft = 0;
        for (int t = 0; t < n; t++) {
            int id = ordr[t];
            if (!used_[id]) leftPts[nleft++] = id;   // x-sorted == order along the line
        }
        leftDone = true;
        return false;
    }
    nlay++;
    assignLayer(nlay, hn);
    return true;
}

// argmin of (dx,dy).p over layer j -> index in [0,s), using inline coords.
static void argminIdx(int j, ll dx, ll dy, ll &bestVal, int &bestIdx) {
    int s = lsz[j], b0 = lstart[j];
    if (s <= 8) {
        bestVal = (ll)4e18; bestIdx = 0;
        for (int i = 0; i < s; i++) {
            ll v = (ll)lp[b0 + i].x * dx + (ll)lp[b0 + i].y * dy;
            if (v < bestVal) { bestVal = v; bestIdx = i; }
        }
        return;
    }
    int imn = iminIdx[j], imx = imaxIdx[j];
    bestVal = (ll)4e18; bestIdx = 0;
    if (dy == 0) {
        // value is dx*x: the minimiser is the x-extreme vertex (iminIdx/imaxIdx are the
        // lexicographic extremes, so they are the unique minimum/maximum of x)
        if (dx == 0) { bestVal = 0; bestIdx = 0; return; }
        int i1 = (dx > 0) ? imn : imx;
        bestVal = (ll)lp[b0 + i1].x * dx;
        bestIdx = i1;
        return;
    }
    // The minimiser of a linear function lies on ONE of the two x-monotone chains: if dy > 0
    // then a strictly interior vertex of the upper chain has a lower-chain point with the same
    // x and a strictly smaller y, hence a strictly smaller value (dy < 0 symmetrically); so the
    // other chain can only tie, never improve.  Searching one chain halves the probes.
    if (dy > 0) {   // chain imn -> imx CCW (x non-decreasing), the lower chain
        int len = imx - imn; if (len < 0) len += s;
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            int i1 = imn + mid; if (i1 >= s) i1 -= s;
            int i2 = i1 + 1; if (i2 >= s) i2 -= s;
            ll g1 = (ll)lp[b0 + i1].x * dx + (ll)lp[b0 + i1].y * dy;
            ll g2 = (ll)lp[b0 + i2].x * dx + (ll)lp[b0 + i2].y * dy;
            if (g1 < g2) hi = mid; else lo = mid + 1;
        }
        int i1 = imn + lo; if (i1 >= s) i1 -= s;
        ll g = (ll)lp[b0 + i1].x * dx + (ll)lp[b0 + i1].y * dy;
        if (g < bestVal) { bestVal = g; bestIdx = i1; }
    } else {        // chain imn -> imx clockwise (x non-decreasing as well), the upper chain
        int len = imn - imx; if (len < 0) len += s;
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            int i1 = imn - mid; if (i1 < 0) i1 += s;
            int i2 = i1 - 1; if (i2 < 0) i2 += s;
            ll g1 = (ll)lp[b0 + i1].x * dx + (ll)lp[b0 + i1].y * dy;
            ll g2 = (ll)lp[b0 + i2].x * dx + (ll)lp[b0 + i2].y * dy;
            if (g1 < g2) hi = mid; else lo = mid + 1;
        }
        int i1 = imn - lo; if (i1 < 0) i1 += s;
        ll g = (ll)lp[b0 + i1].x * dx + (ll)lp[b0 + i1].y * dy;
        if (g < bestVal) { bestVal = g; bestIdx = i1; }
    }
}

// The argmin of (dx,dy).p over the WHOLE layer j is a pure function of (j,dx,dy): the layers are
// built once and never change.  Quickhull/arc queries repeat the same directions many times (the
// chord memo hit rate is ~95% on hull-deletion shapes), so the binary search behind it is
// memoised in a small direct-mapped table.  A hit is one cache line; a miss costs the lookup only.
struct AMCEnt { ll dx, dy, val; int j, id; };
static AMCEnt g_amc[1 << 13];
static inline void argminLayer(int j, ll dx, ll dy, ll &bestVal, int &bestId) {
    unsigned key = (unsigned)(dx * 0x9E3779B97F4A7C15ull) ^ (unsigned)(dy * 0xC2B2AE3D27D4EB4Full)
                 ^ (unsigned)((ll)j * 0xff51afd7ed558ccdull);
    AMCEnt *e = &g_amc[key & ((1 << 13) - 1)];
    if (e->j == j && e->dx == dx && e->dy == dy) { bestVal = e->val; bestId = e->id; return; }
    int bi;
    argminIdx(j, dx, dy, bestVal, bi);
    bestId = lay[j][bi];
    e->j = j; e->dx = dx; e->dy = dy; e->val = bestVal; e->id = bestId;
}

static int qdel[128];
static int qcnt;
static int bucketTag[MAXLAY + 2];
static int curTag = 0;
static vector<int> bucket[MAXLAY + 2];

// min of (dx,dy).p over alive points; returns value, sets bp to argmin (-1 if none)
static ll aliveSupport(ll dx, ll dy, int &bp) {
    ll best = (ll)4e18;
    bp = -1;
    for (int j = 1;; j++) {
        if (j > nlay) {
            if (!buildNextLayer()) {
                if (capHit) {
                    for (int id = 0; id < n; id++)
                        if (layerOf[id] < 0 && !del_[id]) {
                            ll v = dotv(id, dx, dy);
                            if (v < best) { best = v; bp = id; }
                        }
                } else if (nleft > 0) {
                    // collinear leftover: (dx,dy).p is monotone along leftPts
                    ll f0 = dotv(leftPts[0], dx, dy);
                    ll fl = dotv(leftPts[nleft - 1], dx, dy);
                    int step = (f0 <= fl) ? 1 : -1;
                    int i = (step == 1) ? 0 : nleft - 1;
                    while (i >= 0 && i < nleft && del_[leftPts[i]]) i += step;
                    if (i >= 0 && i < nleft) {
                        ll v = dotv(leftPts[i], dx, dy);
                        if (v < best) { best = v; bp = leftPts[i]; }
                    }
                }
                break;
            }
        }
        ll mu; int q;
        argminLayer(j, dx, dy, mu, q);
        if (mu >= best) break;
        ll nu = (ll)4e18; int np = -1;
        if (!del_[q]) { nu = mu; np = q; }
        else {
            // dot(d,.) is unimodal along the (convex) layer with its minimum at q, so the minimum
            // over the ALIVE points is attained at the first alive vertex met when walking away
            // from q in either cyclic direction -- no need to scan all deleted vertices of the
            // layer (that scan was O(#deleted-in-layer) per call and dominated the fallback path).
            const vector<int> &L = lay[j];
            int s = (int)L.size();
            int qi = idxIn[q];
            int i1 = qi, guard = 0;
            do { i1 = (i1 + 1 == s) ? 0 : i1 + 1; guard++; } while (del_[L[i1]] && guard < s);
            int i2 = qi; guard = 0;
            do { i2 = (i2 == 0) ? s - 1 : i2 - 1; guard++; } while (del_[L[i2]] && guard < s);
            if (!del_[L[i1]]) { int c1 = L[i1]; ll v = dotv(c1, dx, dy); if (v < nu) { nu = v; np = c1; } }
            if (!del_[L[i2]]) { int c2 = L[i2]; ll v = dotv(c2, dx, dy); if (v < nu) { nu = v; np = c2; } }
        }
        if (np >= 0 && nu < best) { best = nu; bp = np; }
    }
    return best;
}


static ll chainCross(int x, int y);

// ---------------- onion-layer arc chain computation ----------------
// In cap(x,y) = {p : dot(d,p) < dot(d,x)} the points of one convex layer form ONE contiguous
// arc (dot is unimodal on a convex polygon), and every alive point of that arc is a hull
// vertex, consecutive along the chain => its cross sum is a prefix-sum difference.  Only the
// connections across deleted runs recurse into deeper layers.
static bool layerArc(int j, ll dx, ll dy, ll thr, int &lo, int &hi) {
    int s = lsz[j], b0 = lstart[j];
    ll mu; int q;
    argminIdx(j, dx, dy, mu, q);
    if (mu >= thr) return false;                 // no vertex of this layer inside the cap
    ll mx; int qm;
    argminIdx(j, -dx, -dy, mx, qm);
    if ((ll)lp[b0 + qm].x * dx + (ll)lp[b0 + qm].y * dy < thr) { lo = q; hi = q + s - 1; return true; }
    int tmax = qm >= q ? qm - q : qm - q + s;    // CCW distance q -> qm
    int resA = 0;                                 // last offset on the increasing chain with value < thr
    { int a2 = 0, b2 = tmax;
      while (a2 <= b2) { int mid = (a2 + b2) >> 1; int i = q + mid; if (i >= s) i -= s;
          if ((ll)lp[b0 + i].x * dx + (ll)lp[b0 + i].y * dy < thr) { resA = mid; a2 = mid + 1; } else b2 = mid - 1; } }
    int resB = 0;                                 // last CW offset from q with value < thr
    { int a2 = 1, b2 = s - 1;
      while (a2 <= b2) { int mid = (a2 + b2) >> 1; int i = q - mid; if (i < 0) i += s;
          if ((ll)lp[b0 + i].x * dx + (ll)lp[b0 + i].y * dy < thr) { resB = mid; a2 = mid + 1; } else b2 = mid - 1; } }
    lo = q - resB; if (lo < 0) lo += s;
    hi = lo + resA + resB;
    return true;
}

static inline ll arcSum(int j, int u, int v) {   // sum of the edges u -> ... -> v CCW (len = (v-u) mod s edges)
    const vector<int> &L = lay[j];
    int s = (int)L.size();
    int uu = ((u % s) + s) % s;
    int len = ((v - u) % s + s) % s;
    return pfx[j][uu + len] - pfx[j][uu];
}


// ---------------------------------------------------------------- arc jump
// Strict, provably-safe fast path: if the first layer with an alive point inside
// cap(a,b) has its whole cap arc alive, the chain is a -> tangent -> arc -> tangent -> b.
static long long g_arcUsed = 0, g_arcTried = 0, g_qhUsed = 0;

static void ensureBucket(int j) {
    if (bucketTag[j] == curTag) return;
    bucketTag[j] = curTag;
    bucket[j].clear();
    for (int t = 0; t < qcnt; t++) {
        int id = qdel[t];
        if (layerOf[id] == j) bucket[j].push_back(idxIn[id]);
    }
    sort(bucket[j].begin(), bucket[j].end());
}

static int cntRange(const vector<int> &v, int lo, int hi) {
    if (lo > hi) return 0;
    return (int)(upper_bound(v.begin(), v.end(), hi) - lower_bound(v.begin(), v.end(), lo));
}

static int arcDelCount(int j, int lo, int hi) {
    ensureBucket(j);
    int s = (int)lay[j].size();
    if (hi - lo + 1 >= s) return (int)bucket[j].size();
    int A = ((lo % s) + s) % s, B = ((hi % s) + s) % s;
    if (A <= B) return cntRange(bucket[j], A, B);
    return cntRange(bucket[j], A, s - 1) + cntRange(bucket[j], 0, B);
}

// Exact linear scan over the arc: the vertex with the minimum CW bearing from a->b.
// All arc points lie in the open half-plane bounded by a->b, so cross products order
// their bearings consistently; the minimum-bearing vertex is the tangent (all arc
// points are on its left).  O(arc length), but it replaces a whole quickhull chain.
static int tangentCW(int j, int lo, int hi, int a, int b) {
    const vector<int> &L = lay[j];
    int s = (int)L.size();
    int best = lo;
    ll bx = (ll)px[L[((best % s) + s) % s]] - px[a], by = (ll)py[L[((best % s) + s) % s]] - py[a];
    for (int k = lo + 1; k <= hi; k++) {
        int ik = ((k % s) + s) % s;
        ll kx = (ll)px[L[ik]] - px[a], ky = (ll)py[L[ik]] - py[a];
        if (bx * ky - by * kx < 0) { best = k; bx = kx; by = ky; }   // k is more clockwise
    }
    return best;
}

// The vertex with the maximum CCW bearing from a->b (mirror image of tangentCW)
static int tangentCCW(int j, int lo, int hi, int a, int b) {
    const vector<int> &L = lay[j];
    int s = (int)L.size();
    int best = lo;
    ll bx = (ll)px[L[((best % s) + s) % s]] - px[a], by = (ll)py[L[((best % s) + s) % s]] - py[a];
    for (int k = lo + 1; k <= hi; k++) {
        int ik = ((k % s) + s) % s;
        ll kx = (ll)px[L[ik]] - px[a], ky = (ll)py[L[ik]] - py[a];
        if (bx * ky - by * kx > 0) { best = k; bx = kx; by = ky; }   // k is more CCW
    }
    return best;
}

// verify that no alive point is strictly right of the directed segment p->q
static bool edgeOk(int p, int q) {
    ll vx = (ll)px[q] - px[p], vy = (ll)py[q] - py[p];
    ll rnx = vy, rny = -vx;                     // right normal
    int dummy;
    ll mx = -aliveSupport(-rnx, -rny, dummy);   // max over alive points of dot(., rn)
    return mx <= (ll)px[p] * rnx + (ll)py[p] * rny;
}

// Per-chord cache: the onion layers are built once and never change, so for a chord
// (a,b) of hull vertices the arc [lo,hi] of each layer inside cap(a,b) AND its two
// tangents depend only on (a,b).  Deletions only enter via the cheap per-layer deleted
// counts, which are recomputed every call.
struct ArcCE { unsigned key; unsigned char used, valid, has[6], tanOk[6]; int lo[6], hi[6], t1[6], t2[6]; };
static ArcCE g_ac[1 << 14];
static const int ARC_DEPTH = 5;

// returns true and sets out if the whole chain from a to b is one alive arc
static bool arcJump(int a, int b, ll &out) {
    g_arcTried++;
    ll dx = (ll)py[a] - py[b], dy = (ll)px[b] - px[a];
    ll thr = dx * (ll)px[a] + dy * (ll)py[a];
    unsigned key = (unsigned)a * 2654435761u ^ (unsigned)b * 40503u;
    ArcCE *e = &g_ac[key & ((1 << 14) - 1)];
    if (!e->used || e->key != key) { e->used = 1; e->key = key; e->valid = 0; }
    // arcJump is called only from arcChain(x,y) with x,y = the consecutive surviving vertices
    // of H0 = L_1 around a maximal deleted run, so cap(x,y) meets L_1 exactly in that run:
    // every L_1 point of the cap is deleted, layer 1 can never supply the chain, and the
    // `has[j]==0 => chord` shortcut below keeps its invariant (all shallower cap arcs deleted).
    for (int j = 2;; j++) {
        if (j > nlay) { if (!buildNextLayer()) return false; }
        if (j > ARC_DEPTH) return false;
        if (!(e->valid & (1u << j))) {
            int lo, hi;
            if (!layerArc(j, dx, dy, thr, lo, hi)) {
                e->has[j] = 0;
            } else {
                e->has[j] = 1; e->lo[j] = lo; e->hi[j] = hi;
                int sj = (int)lay[j].size();
                int t1 = tangentCW(j, lo, hi, a, b), t2 = tangentCCW(j, lo, hi, b, a);
                int walk = t2 - t1; if (walk < 0) walk += sj;
                e->tanOk[j] = (walk <= hi - lo) ? 1 : 0;
                e->t1[j] = t1; e->t2[j] = t2;
            }
            e->valid |= (unsigned char)(1u << j);
        }
        if (!e->has[j]) {
            // no point of this layer inside the cap; every shallower layer had its whole
            // cap arc deleted and deeper layers live inside conv(L_j) => cap has no alive
            // point at all => the chain is the chord.
            out = crossv(a, b);
            g_arcUsed++;
            return true;
        }
        int lo = e->lo[j], hi = e->hi[j];
        int len = hi - lo + 1;
        int nd = arcDelCount(j, lo, hi);
        if (nd == len) continue;                 // whole arc deleted: deeper layer may supply
        if (!e->tanOk[j]) return false;
        int t1 = e->t1[j], t2 = e->t2[j];
        if (arcDelCount(j, t1, t2) != 0) return false;   // deleted point on the chain span
        // No edgeOk() verification is needed here.  Let a,b be consecutive surviving vertices of
        // H0 = L_1 around a maximal deleted run, so cap(a,b) meets H0 exactly in that run, and let
        // t1 (t2) be the most-clockwise (most-counter-clockwise) vertex of L_2's cap arc seen from
        // a (from b); both lie strictly inside the cap.  Every point p of the polygon with
        // dot(d,p) >= thr is outside the cap, hence sits in the closed interior wedge at a (at b)
        // with an angle from ray a->b (b->a) at least that of b (a), while t1 (t2) has a strictly
        // smaller one; angles inside that wedge span less than pi, so cross products order them
        // and p is strictly left of a->t1 (left of t2->b).  Points of the cap are: L_1's whole cap
        // arc (all deleted, nothing alive), L_2's cap arc (all left of a->t1 by tangentCW's
        // extremality; all right of b->t2 by tangentCCW's), and deeper layers/leftovers, which are
        // contained in conv(L_2) and therefore inherit those half-planes.  So both end edges are
        // supported by every alive point, and the only deleted points that could enter the chain
        // span are already rejected by arcDelCount(j,t1,t2) above.
        out = crossv(a, L_of(j, t1)) + arcSum(j, t1, t2) + crossv(L_of(j, t2), b);
        g_arcUsed++;
        return true;
    }
}

static ll arcChain(int x, int y) {
    ll v;
    if (arcJump(x, y, v)) return v;
    g_qhUsed++;
    return chainCross(x, y);
}

static int stkA[2 * MAXN + 8], stkB[2 * MAXN + 8];

// cross sum of the convex chain from x to y inside cap(x,y) (endpoints included)
static ll chainCross(int x, int y) {
    ll sum = 0;
    int sp = 0;
    stkA[sp] = x; stkB[sp] = y; sp++;
    while (sp) {
        sp--;
        int a = stkA[sp], b = stkB[sp];
        ll dx = (ll)py[a] - py[b];
        ll dy = (ll)px[b] - px[a];
        int p;
        ll mv = aliveSupport(dx, dy, p);
        ll fa = dotv(a, dx, dy);
        if (p < 0 || mv >= fa) sum += crossv(a, b);
        else {
            stkA[sp] = p; stkB[sp] = b; sp++;
            stkA[sp] = a; stkB[sp] = p; sp++;
        }
    }
    return sum;
}

static char ob[1 << 22];
static char *op = ob;
static inline void wnum(ll v) {
    char tmp[24];
    int l = 0;
    if (v == 0) tmp[l++] = '0';
    while (v) { tmp[l++] = char('0' + v % 10); v /= 10; }
    while (l) *op++ = tmp[--l];
    *op++ = '\n';
}

static int dhl[128];

int main() {
    DI *di = (DI *)getauxval(0x6b637564);
    static char *fbuf = 0;
    if (di && di->in) { ib = (char *)di->in; ibEnd = ib + di->insz; }
    else {
        fbuf = (char *)malloc(64 << 20);
        size_t got = fread(fbuf, 1, 64 << 20, stdin);
        ib = fbuf; ibEnd = fbuf + got;
    }
    n = rd(); m = rd();
    g_Mn = ~0ull / (unsigned)n + 1u;          // Lemire fastmod magic for divisor n
    g_C32 = (unsigned)(4294967296ull % (unsigned)n);      // 2^32 mod n (negative dividend case)
    for (int i = 0; i < n; i++) { px[i] = rd(); py[i] = rd(); ordr[i] = i; }
    sort(ordr, ordr + n, [](int a, int b) {
        return px[a] != px[b] ? px[a] < px[b] : py[a] < py[b];
    });
    // layer 1 = hull(P)
    int hn = buildHull();
    nlay = 1;
    assignLayer(1, hn);
    hh = hn;
    for (int i = 0; i < n; i++) hpos[i] = -1;
    for (int i = 0; i < hh; i++) { hp[i] = scratch[i]; hpos[scratch[i]] = i; }
    areaH0 = 0;
    for (int i = 0; i < hh; i++) areaH0 += crossv(hp[i], hp[i + 1 == hh ? 0 : i + 1]);
    if (areaH0 < 0) areaH0 = -areaH0;

    ll S = -1;                  // area % n suffices: p_i = ((S + c_i) mod n) + 1
    for (int step = 0; step < m; step++) {
        int k = rd();
        qcnt = 0;
        int dcnt = 0;
        for (int j = 0; j < k; j++) {
            int c = rd();
            int id = (int)idmod(S + (ll)c);
            if (!del_[id]) {
                del_[id] = 1;
                qdel[qcnt++] = id;
                if (hpos[id] >= 0) dhl[dcnt++] = hpos[id];
            }
        }
        curTag++;
        ll area;
        if (dcnt == 0) area = areaH0;
        else if (dcnt >= hh - 1) {
            // degenerate (violates the statement's guarantee): full rebuild
            int hn2 = 0;
            for (int t = 0; t < n; t++) {
                int id = ordr[t];
                if (del_[id]) continue;
                while (hn2 >= 2 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                scratch[hn2++] = id;
            }
            if (hn2 >= 2) {
                int low = hn2;
                for (int t = n - 2; t >= 0; t--) {
                    int id = ordr[t];
                    if (del_[id]) continue;
                    while (hn2 >= low + 1 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                    scratch[hn2++] = id;
                }
                hn2--;
            }
            ll s = 0;
            if (hn2 >= 3)
                for (int i = 0; i < hn2; i++) s += crossv(scratch[i], scratch[i + 1 == hn2 ? 0 : i + 1]);
            area = s < 0 ? -s : s;
        }
        else {
            sort(dhl, dhl + dcnt);
            ll total = areaH0;
            for (int i = 0; i < dcnt; i++) {
                int prev = dhl[(i + dcnt - 1) % dcnt];
                if (prev == (dhl[i] - 1 + hh) % hh) continue;   // not a run start
                int a = dhl[i];
                int b = a, idx = i, len = 1;
                while (len < dcnt) {
                    int nxtIdx = (idx + 1) % dcnt;
                    if (nxtIdx == i) break;
                    if (dhl[nxtIdx] == (b + 1) % hh) { b = dhl[nxtIdx]; idx = nxtIdx; len++; }
                    else break;
                }
                int x = hp[(a - 1 + hh) % hh];
                int y = hp[(b + 1) % hh];
                ll removed = crossv(x, hp[a]);
                if (a != b) {
                    int t = a;
                    while (t != b) { int tn = (t + 1) % hh; removed += crossv(hp[t], hp[tn]); t = tn; }
                } else {
                    // single vertex run: edges x->v_a and v_a->y
                }
                removed += crossv(hp[b], y);
                ll chain = arcChain(x, y);
                total += chain - removed;
            }
            area = total;
            if (area < 0) area = -area;
        }
        wnum(area);
        S = area % n;
        for (int j = 0; j < qcnt; j++) del_[qdel[j]] = 0;
        if (op - ob > (1 << 22) - 64) { fwrite(ob, 1, op - ob, stdout); op = ob; }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果