代码

// NOI2017 分身术 - onion layers + t-separated arc enumeration + O(log) lower-bridge merge.
// Compile with -DTEST to self-test against brute on stdin (gen.py format).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 100005;
static const int MAXK = 130;
static const int PEEL = 105;  // recursion depth <= k <= 100, so peel 105 convex layers max
static ll X[MAXN], Y[MAXN];
static inline ll crs3(int a,int b,int c){ return (X[b]-X[a])*(Y[c]-Y[b])-(Y[b]-Y[a])*(X[c]-X[b]); }
static inline ll cross2(int a,int b){ return X[a]*Y[b]-Y[a]*X[b]; }
static inline ll crsP(int o,int a,int b){ return (X[a]-X[o])*(Y[b]-Y[o])-(Y[a]-Y[o])*(X[b]-X[o]); }

static int K;
static vector<int> vert[MAXK];
static int h[MAXK];
static vector<ll> pref[MAXK];
static int layer_of[MAXN], pos_of[MAXN];
static int loLen[MAXK];
static vector<pair<int,int>> dels;
static int delMark[MAXN];
static int delStamp = 0;
static int n, m;

template<class F>
static void extrema(int d, const F& g, int& mn, int& mx){
    int hd = h[d], LL = loLen[d];
    auto maxOn = [&](int lo,int hi){ int Ol=lo,Or=hi,l=lo,r=hi; while(r-l>2){ int m1=l+(r-l)/3, m2=r-(r-l)/3; if(g(m1)<g(m2)) l=m1; else r=m2; } int e=l; for(int t=l;t<=r;t++) if(g(t)>g(e)) e=t; if(g(Ol)>g(e)) e=Ol; if(g(Or)>g(e)) e=Or; return e; };
    auto minOn = [&](int lo,int hi){ int Ol=lo,Or=hi,l=lo,r=hi; while(r-l>2){ int m1=l+(r-l)/3, m2=r-(r-l)/3; if(g(m1)>g(m2)) l=m1; else r=m2; } int e=l; for(int t=l;t<=r;t++) if(g(t)<g(e)) e=t; if(g(Ol)<g(e)) e=Ol; if(g(Or)<g(e)) e=Or; return e; };
    int M = maxOn(0, LL-1);
    if(LL < hd){ int M2 = maxOn(LL, hd-1); if(g(M2) > g(M)) M = M2; }
    int m = minOn(0, LL-1);
    if(LL < hd){ int m2 = minOn(LL, hd-1); if(g(m2) < g(m)) m = m2; }
    mn = m; mx = M;
}

static inline ll tval(int A,int B,int p){ return (X[p]-X[A])*(X[B]-X[A]) + (Y[p]-Y[A])*(Y[B]-Y[A]); }
static inline ll hval(int A,int B,int p){ return crs3(A,B,p); }

// lower-hull arc of layer d (h>=3) w.r.t. chord A,B, returned t-increasing: (s,len,step).
// step=+1: chain[k]=vert[d][(s+k)%h]; step=-1: vert[d][(s-k+h)%h].
// Returns false if empty; fallback set on collinear ambiguity.
static bool lowerHullArc(int d, int A, int B, int& s, int& len, int& step, bool& fallback, bool& allBelow){
    int hd = h[d];
    auto g = [&](int t){ return hval(A,B,vert[d][t % hd]); };
    int m, M; extrema(d, g, m, M);
    ll gM = g(M), gm = g(m);
    allBelow = false;
    if(gm > 0) return false;   // all above AB
    if(gM < 0){                // all below: bottom arc from tmin..tmax through hmin
        allBelow = true;
        auto gt = [&](int t){ return tval(A,B,vert[d][t % hd]); };
        int tmn, tmx; extrema(d, gt, tmn, tmx);
        int a = tmn, b = tmx;
        int d1 = (m - a + hd) % hd;
        int d2 = (b - a + hd) % hd;
        if(d1 <= d2){ s = a; step = +1; len = d2 + 1; }
        else { s = a; step = -1; len = (hd - d2) + 1; }
        return true;
    }
    // intersecting
    if(gM == 0 || gm == 0){ fallback = true; return false; }
    int start=M, end=m; if(end<start) end+=hd;
    int lo=start, hi=end;
    while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
    int fa = lo % hd;
    start=m; end=M; if(end<start) end+=hd;
    lo=start; hi=end;
    while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
    int fb = (lo-1+hd) % hd;
    // The below-AB arc [fa..fb] must be t-monotone for the bridge merge.
    // t is bitonic along the convex arc, so compare the t-slopes at the two ends:
    // opposite signs => interior t-extreme => non-monotone => fallback.
    if(fa != fb){
        int na = (fa + 1) % hd;
        int pb = (fb - 1 + hd) % hd;
        ll d0 = tval(A,B,vert[d][na]) - tval(A,B,vert[d][fa]);
        ll dL = tval(A,B,vert[d][fb]) - tval(A,B,vert[d][pb]);
        if((d0 > 0 && dL < 0) || (d0 < 0 && dL > 0) || d0 == 0 || dL == 0){
            fallback = true; return false;
        }
    }
    int a = fa, b = fb; if(b < a) b += hd;
    ll ta = tval(A,B,vert[d][a%hd]), tb = tval(A,B,vert[d][b%hd]);
    if(ta <= tb){ s = fa; step = +1; len = b-a+1; }
    else { s = fb; step = -1; len = b-a+1; }
    return true;
}

// ---- implicit chains ----
struct Piece { int d, s, step, kStart, kLen; };
struct Chain {
    vector<Piece> pc;
    vector<int> szPref;
    vector<ll> csPref;   // csPref[i] = cross-sum of pieces[0..i-1] + bridge edges among them
    int size() const { return szPref.empty() ? 0 : szPref.back(); }
    ll total() const { return csPref.empty() ? 0 : csPref.back(); }
};

static inline int piecePoint(const Piece& p, int k){
    int hd = h[p.d];
    int idx = p.s + (p.kStart + k) * p.step;
    idx %= hd; if(idx < 0) idx += hd;
    return vert[p.d][idx];
}
static inline int pieceFirst(const Piece& p){ return piecePoint(p, 0); }
static inline int pieceLast(const Piece& p){ return piecePoint(p, p.kLen - 1); }
static ll pieceCS(const Piece& p){
    int hd = h[p.d];
    int len = p.kLen;
    if(len <= 1) return 0;
    if(p.step == +1){
        int b = p.s + p.kStart;
        return pref[p.d][b + len - 1] - pref[p.d][b];
    } else {
        int Rh = p.s - p.kStart + hd;
        int Lh = p.s - p.kStart - len + 1 + hd;
        return pref[p.d][Lh] - pref[p.d][Rh];
    }
}
static int chainPoint(const Chain& c, int k){
    int idx = (int)(upper_bound(c.szPref.begin(), c.szPref.end(), k) - c.szPref.begin()) - 1;
    return piecePoint(c.pc[idx], k - c.szPref[idx]);
}
static void rebuildChainCS(Chain& c){
    int np = (int)c.pc.size();
    c.csPref.assign(np+1, 0);
    for(int i=0;i<np;i++){
        ll v = 0;
        if(i > 0) v += cross2(pieceLast(c.pc[i-1]), pieceFirst(c.pc[i]));
        v += pieceCS(c.pc[i]);
        c.csPref[i+1] = c.csPref[i] + v;
    }
}
static ll chainPrefixCS(const Chain& c, int cnt){ // cross-sum of first cnt points (cnt-1 edges)
    if(cnt <= 1) return 0;
    int idx = (int)(upper_bound(c.szPref.begin(), c.szPref.end(), cnt-1) - c.szPref.begin()) - 1;
    ll s = c.csPref[idx];
    if(idx > 0) s += cross2(pieceLast(c.pc[idx-1]), pieceFirst(c.pc[idx]));
    const Piece& p = c.pc[idx];
    Piece q = p; q.kLen = (cnt-1) - c.szPref[idx] + 1;
    s += pieceCS(q);
    return s;
}
static ll chainSuffixCS(const Chain& c, int start){ // cross-sum of points start..end
    int sz = c.size();
    if(start >= sz-1) return 0;
    return c.total() - chainPrefixCS(c, start+1);
}

static void chainFromPoint(int p, Chain& c){
    c.pc.clear(); c.szPref.clear(); c.csPref.clear();
    c.pc.push_back({layer_of[p], pos_of[p], +1, 0, 1});
    c.szPref.push_back(0); c.szPref.push_back(1);
    rebuildChainCS(c);
}
static void chainFromArc(int d, int s, int len, int step, Chain& c){
    c.pc.clear(); c.szPref.clear(); c.csPref.clear();
    if(len <= 0){ rebuildChainCS(c); return; }
    c.pc.push_back({d, s, step, 0, len});
    c.szPref.push_back(0); c.szPref.push_back(len);
    rebuildChainCS(c);
}

static int lowerTangentJ(int oi, const Chain& B){
    int q = B.size();
    int lo=0, hi=q-1;
    while(lo<hi){
        int mid=(lo+hi)>>1;
        if(crsP(oi, chainPoint(B,mid), chainPoint(B,mid+1)) < 0) lo=mid+1; else hi=mid;
    }
    return lo;
}
static pair<int,int> lowerBridge(const Chain& A, const Chain& B){
    int p = A.size();
    if(p == 1) return {0, lowerTangentJ(chainPoint(A,0), B)};
    int lo=0, hi=p-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j = lowerTangentJ(chainPoint(A,mid), B);
        bool ok = (mid==0) || (crs3(chainPoint(A,mid-1), chainPoint(A,mid), chainPoint(B,j)) > 0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    int i=ans, j=lowerTangentJ(chainPoint(A,i), B);
    return {i,j};
}
static void mergeChains(const Chain& A, const Chain& B, int i, int j, Chain& out){
    out.pc.clear(); out.szPref.clear();
    int idxA = (int)(upper_bound(A.szPref.begin(), A.szPref.end(), i) - A.szPref.begin()) - 1;
    for(int t=0;t<idxA;t++) out.pc.push_back(A.pc[t]);
    {
        const Piece& p = A.pc[idxA];
        Piece q = p; q.kLen = i - A.szPref[idxA] + 1;
        if(q.kLen > 0) out.pc.push_back(q);
    }
    int idxB = (int)(upper_bound(B.szPref.begin(), B.szPref.end(), j) - B.szPref.begin()) - 1;
    {
        const Piece& p = B.pc[idxB];
        Piece q = p; q.kStart = p.kStart + (j - B.szPref[idxB]); q.kLen = p.kLen - (j - B.szPref[idxB]);
        if(q.kLen > 0) out.pc.push_back(q);
    }
    for(int t=idxB+1;t<(int)B.pc.size();t++) out.pc.push_back(B.pc[t]);
    out.szPref.push_back(0);
    for(auto& p : out.pc) out.szPref.push_back(out.szPref.back() + p.kLen);
    rebuildChainCS(out);
}

static inline int arcPoint(int d, int s, int step, int k){
    int hd = h[d];
    int idx = s + k*step; idx %= hd; if(idx<0) idx += hd;
    return vert[d][idx];
}

// enumerate surviving arcs of layers d.. for chord A,B, clipped to t in [tL,tR], t-increasing.
static void collectArcs(int d, int A, int B, ll tL, ll tR, vector<Piece>& out, bool& fallback){
    if(d >= K) return;
    int hd = h[d];
    if(hd < 3){
        // degenerate layer: at most 2 points. add below-AB points (in [tL,tR]) as single points.
        int tmp[4];
        int cnt = 0;
        for(int t=0;t<hd;t++){
            int p = vert[d][t];
            if(delMark[p] == delStamp) continue;
            if(hval(A,B,p) < 0){
                ll tv = tval(A,B,p);
                if(tv >= tL && tv <= tR) tmp[cnt++] = p;
            }
        }
        if(cnt == 2){
            ll t0 = tval(A,B,tmp[0]), t1 = tval(A,B,tmp[1]);
            if(t0 > t1) swap(tmp[0], tmp[1]);
        }
        for(int i=0;i<cnt;i++){
            out.push_back({layer_of[tmp[i]], pos_of[tmp[i]], +1, 0, 1});
        }
        return;
    }
    int s, len, step;
    bool allBelow = false;
    if(!lowerHullArc(d, A, B, s, len, step, fallback, allBelow)) return;
    if(allBelow){
        // layer entirely below AB: deletions on it can expose "top" vertices -> fallback.
        for(auto& pr : dels) if(pr.first == d){ fallback = true; return; }
    }
    // clip to [tL,tR] (t increasing in k)
    int klo = len, khi = -1;
    {
        int l=0, r=len-1;
        while(l<=r){ int mid=(l+r)>>1; if(tval(A,B,arcPoint(d,s,step,mid)) >= tL){ klo=mid; r=mid-1; } else l=mid+1; }
        l=0; r=len-1;
        while(l<=r){ int mid=(l+r)>>1; if(tval(A,B,arcPoint(d,s,step,mid)) <= tR){ khi=mid; l=mid+1; } else r=mid-1; }
    }
    if(klo > khi) return;
    int sllen = khi - klo + 1;
    // deleted offsets within sub-arc [klo,khi]
    vector<int> dp;
    for(auto& pr : dels){
        if(pr.first != d) continue;
        int p = pr.second;
        int k;
        if(step==+1) k = (p - s + hd) % hd;
        else k = (s - p + hd) % hd;
        if(k >= klo && k <= khi) dp.push_back(k - klo);
    }
    sort(dp.begin(), dp.end());
    dp.erase(unique(dp.begin(), dp.end()), dp.end());
    int cur = 0, i = 0;
    while(i < (int)dp.size()){
        int pk = dp[i], qk = pk;
        while(i+1 < (int)dp.size() && dp[i+1] == qk+1) qk = dp[++i];
        // surviving piece [cur, pk-1]
        if(pk-1 >= cur){
            int ss = arcPoint(d, s, step, klo + cur);
            // find ss's layer pos and store as a t-increasing piece starting at ss
            out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, pk - cur});
        }
        // recurse for gap [pk, qk]
        ll tL2 = (pk > 0) ? tval(A,B,arcPoint(d,s,step,klo+pk-1)) : tL;
        ll tR2 = (qk+1 < sllen) ? tval(A,B,arcPoint(d,s,step,klo+qk+1)) : tR;
        collectArcs(d+1, A, B, tL2, tR2, out, fallback);
        cur = qk + 1;
        i++;
    }
    if(cur <= sllen-1){
        out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, sllen - cur});
    }
}

// fallback: materialize + sort + graham (same as layers2.cpp)
static vector<int> E;
static void buildExposed(int d, int A, int B);
static void buildArc(int d2, int lo, int hi, int A, int B){
    int h2 = h[d2];
    vector<int> dp2;
    for(auto& pr : dels){
        if(pr.first != d2) continue;
        int p = pr.second;
        if(lo <= p && p <= hi) dp2.push_back(p);
        if(lo <= p+h2 && p+h2 <= hi) dp2.push_back(p+h2);
    }
    sort(dp2.begin(), dp2.end()); dp2.erase(unique(dp2.begin(),dp2.end()),dp2.end());
    if(dp2.empty()){ for(int t=lo;t<=hi;t++) E.push_back(vert[d2][t % h2]); return; }
    int cur=lo, i=0;
    while(i < (int)dp2.size()){
        int p=dp2[i], q=p;
        while(i+1 < (int)dp2.size() && dp2[i+1]==q+1) q=dp2[++i];
        for(int t=cur;t<=p-1;t++) E.push_back(vert[d2][t % h2]);
        buildExposed(d2, A, B);
        cur=q+1; i++;
    }
    for(int t=cur;t<=hi;t++) E.push_back(vert[d2][t % h2]);
}
static int findArcSlow(int A, int B, int d2, int& fa, int& fb){
    int h2 = h[d2];
    int e0=-1; bool anyNon=false;
    for(int t=0;t<h2;t++){ if(crs3(A,B,vert[d2][t])<0){ if(e0<0)e0=t; } else anyNon=true; }
    if(e0==-1) return 0;
    if(!anyNon){ fa=0; fb=h2-1; return 1; }
    fa=e0; fb=e0;
    for(int st=0; st<h2 && crs3(A,B,vert[d2][(fb+1)%h2])<0; st++) fb=(fb+1)%h2;
    for(int st=0; st<h2 && crs3(A,B,vert[d2][(fa-1+h2)%h2])<0; st++) fa=(fa-1+h2)%h2;
    return 1;
}
static int findArcFast(int A, int B, int d2, int& fa, int& fb){
    int h2=h[d2];
    if(h2<3) return -1;
    int LL=loLen[d2];
    auto g=[&](int t){ return crs3(A,B,vert[d2][t%h2]); };
    int m,M; extrema(d2, g, m, M);
    ll gM=g(M), gm=g(m);
    if(gM<0){ fa=0; fb=h2-1; return 1; }
    if(gm>0) return 0;
    if(gM==0||gm==0) return -1;
    int start=M,end=m; if(end<start) end+=h2;
    int lo=start,hi=end; while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
    fa=lo%h2;
    start=m; end=M; if(end<start) end+=h2;
    lo=start;hi=end; while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
    fb=(lo-1+h2)%h2;
    return 1;
}
static void buildExposed(int d, int A, int B){
    int d2=d+1;
    if(d2>=K) return;
    int fa,fb;
    int r=findArcFast(A,B,d2,fa,fb);
    if(r==0) return;
    if(r==-1){ r=findArcSlow(A,B,d2,fa,fb); if(r==0) return; }
    int lo=fa, hi=(fb>=fa)?fb:fb+h[d2];
    buildArc(d2, lo, hi, A, B);
}
static ll convexChain(int A, vector<int>& E, int B){
    if(E.empty()) return cross2(A,B);
    static vector<int> pts; pts.clear();
    pts=E; pts.push_back(A); pts.push_back(B);
    sort(pts.begin(), pts.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
    pts.erase(unique(pts.begin(),pts.end()),pts.end());
    if(pts.size()<3) return cross2(A,B);
    static int stk[MAXN*2]; int top=0;
    for(int idx:pts){ while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
    int lower=top;
    for(int t=(int)pts.size()-2;t>=0;t--){ int idx=pts[t]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
    top--;
    int iA=-1,iB=-1;
    for(int i=0;i<top;i++){ if(stk[i]==A)iA=i; if(stk[i]==B)iB=i; }
    ll s=0;
    if(stk[(iA+1)%top]==B){
        for(int k=iA;;k=(k-1+top)%top){ int nxt=(k-1+top)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
    } else {
        for(int k=iA;;k=(k+1)%top){ int nxt=(k+1)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==B) break; }
    }
    return s;
}

// main exposed-chain area for a gap (A,B) on L0. A,B are L0 surviving vertices.
static ll exposedChainArea(int A, int B){
    ll tA = tval(A,B,A); // 0
    ll tB = tval(A,B,B); // |AB|^2
    (void)tA;
    // fallback check: any deleted L0 vertex in this gap has t outside [0, tB]? We check during run grouping in caller.
    static vector<Piece> arcs;
    arcs.clear();
    bool fallback = false;
    collectArcs(1, A, B, 0, tB, arcs, fallback);
    if(fallback){
        E.clear();
        buildExposed(0, A, B);
        return convexChain(A, E, B);
    }
    Chain cur; chainFromPoint(A, cur);
    for(auto& p : arcs){
        Chain C; chainFromArc(p.d, p.s, p.kLen, p.step, C);
        auto [i,j] = lowerBridge(cur, C);
        Chain nxt; mergeChains(cur, C, i, j, nxt);
        cur = move(nxt);
    }
    Chain Bc; chainFromPoint(B, Bc);
    auto [i,j] = lowerBridge(cur, Bc);
    Chain fin; mergeChains(cur, Bc, i, j, fin);
    return fin.total();
}

// ---- IO ----
#include <sys/auxv.h>
#include <stdint.h>
struct DuckInfo {
    uint64_t abi_version;
    const char *stdin_ptr; uint64_t stdin_size;
    char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
    char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
    const char *IB_ptr; uint64_t IB_limit;
    char *OB_ptr; uint64_t OB_limit;
    uint64_t tsc_frequency;
} __attribute__((packed));
static const char* ibuf; static size_t ipos=0, ilen=0;
static char* obuf; static size_t opos=0;
static DuckInfo* duck;
static char local_in[1<<22], local_out[1<<22];
static inline char gc(){ if(ipos>=ilen) return 0; return ibuf[ipos++]; }
static inline ll rd(){ char c; while((c=gc()) && (c<'0'||c>'9') && c!='-'); if(c==0) return 0; int s=1; if(c=='-'){s=-1;c=gc();} ll v=0; while(c>='0'&&c<='9'){v=v*10+(c-'0');c=gc();} return s*v; }
static inline void wl(ll v){ if(v==0){obuf[opos++]='0';obuf[opos++]='\n';return;} char t[32];int z=0; if(v<0){obuf[opos++]='-';v=-v;} while(v){t[z++]='0'+(v%10);v/=10;} while(z)obuf[opos++]=t[--z]; obuf[opos++]='\n'; }

static void buildLayers(){
    // sort all indices once, then onion-peel via a doubly-linked list of unused points
    static int order[MAXN];
    for(int i=0;i<n;i++) order[i]=i;
    sort(order, order+n, [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
    static int nxt[MAXN], prv[MAXN];
    for(int i=0;i<n;i++){
        nxt[order[i]] = (i+1 < n) ? order[i+1] : -1;
        prv[order[i]] = (i > 0) ? order[i-1] : -1;
    }
    int head=order[0];
    static vector<int> cur; cur.reserve(n);
    static vector<int> lo, up;
    int rem=n; K=0;
    while(rem>=3 && K<PEEL){
        cur.clear();
        for(int i=head; i!=-1; i=nxt[i]) cur.push_back(i);
        int sz=cur.size();
        lo.clear();
        for(int idx:cur){ while(lo.size()>=2 && crs3(lo[lo.size()-2],lo.back(),idx)<=0) lo.pop_back(); lo.push_back(idx); }
        up.clear();
        for(int t=sz-1;t>=0;t--){ int idx=cur[t]; while(up.size()>=2 && crs3(up[up.size()-2],up.back(),idx)<=0) up.pop_back(); up.push_back(idx); }
        vector<int> H=lo;
        for(int t=1;t<(int)up.size()-1;t++) H.push_back(up[t]);
        if(H.size()<3) break;
        vert[K]=H; h[K]=H.size(); loLen[K]=lo.size();
        pref[K].assign(2*h[K]+2,0);
        for(int t=0;t<2*h[K]+1;t++) pref[K][t+1]=pref[K][t]+cross2(H[t%h[K]],H[(t+1)%h[K]]);
        for(int t=0;t<h[K];t++){ layer_of[H[t]]=K; pos_of[H[t]]=t; }
        for(int t=0;t<h[K];t++){
            int v=H[t];
            if(prv[v]!=-1) nxt[prv[v]]=nxt[v]; else head=nxt[v];
            if(nxt[v]!=-1) prv[nxt[v]]=prv[v];
        }
        K++; rem-=H.size();
    }
    if(rem>0){
        vector<int> rest;
        for(int i=head; i!=-1; i=nxt[i]) rest.push_back(i);
        vert[K]=rest; h[K]=rest.size(); loLen[K]=rest.size();
        pref[K].assign(2*h[K]+2,0);
        for(int t=0;t<2*h[K]+1;t++) pref[K][t+1]=pref[K][t]+cross2(rest[t%h[K]],rest[(t+1)%h[K]]);
        for(int t=0;t<h[K];t++){ layer_of[rest[t]]=K; pos_of[rest[t]]=t; }
        K++;
    }
}

static ll solveQueries(){
    ll S=-1;
    dels.reserve(110);
    ll ret=0;
    for(int q=0;q<m;q++){
        int k=(int)rd();
        dels.clear();
        delStamp++;
        for(int j=0;j<k;j++){
            ll c=rd(); ll v=S+c; v%=n; if(v<0) v+=n;
            int id=(int)v;
            delMark[id] = delStamp;
            if(layer_of[id]>=0) dels.push_back({layer_of[id], pos_of[id]});
        }
        int h0=h[0];
        vector<int> del0;
        for(auto& pr:dels) if(pr.first==0) del0.push_back(pr.second);
        sort(del0.begin(),del0.end());
        del0.erase(unique(del0.begin(),del0.end()),del0.end());
        ll ans=0;
        if(del0.empty()){
            ans=pref[0][h0];
        } else {
            int cnt=del0.size();
            vector<pair<int,int>> runs;
            {
                int i=0;
                while(i<cnt){
                    int p=del0[i], q=p;
                    while(i+1<cnt && del0[i+1]==q+1) q=del0[++i];
                    runs.push_back({p,q}); i++;
                }
            }
            if(runs.size()>=2 && runs[0].first==0 && runs.back().second==h0-1){
                vector<pair<int,int>> merged;
                merged.push_back({runs.back().first, runs[0].second});
                for(int j=1;j<(int)runs.size()-1;j++) merged.push_back(runs[j]);
                runs=merged;
            }
            for(auto& pr:runs){
                int p=pr.first, q=pr.second;
                int A=vert[0][(p-1+h0)%h0];
                int B=vert[0][(q+1)%h0];
                int lo=p-1; if(lo<0) lo+=h0;
                int hi=q+1; if(hi<=lo) hi+=h0;
                ll oldArc=pref[0][hi]-pref[0][lo];
                // fallback check: deleted run vertices t-range within [0, |AB|^2]
                ll tB=tval(A,B,B);
                bool fb=false;
                {
                    int runLen = (q - p + h0) % h0 + 1;
                    for(int st=0; st<runLen; st++){
                        ll tv=tval(A,B,vert[0][(p+st)%h0]);
                        if(tv<0 || tv>tB){ fb=true; break; }
                    }
                }
                ll newChain;
                if(fb){
                    E.clear(); buildExposed(0,A,B); newChain=convexChain(A,E,B);
                } else {
                    newChain=exposedChainArea(A,B);
                }
                ans += newChain - oldArc;
            }
            ans += pref[0][h0];
        }
        if(ans<0) ans=-ans;
        S=ans;
        ret=ans;
        wl(ans);
    }
    return ret;
}

int main(){
    duck=(DuckInfo*)getauxval(0x6b637564);
    if(duck && duck->stdin_ptr){
        ibuf=duck->stdin_ptr; ilen=duck->stdin_size; ipos=0;
        obuf=duck->stdout_ptr; opos=0;
    } else {
        ilen=fread(local_in,1,sizeof(local_in),stdin); ibuf=local_in; ipos=0;
        obuf=local_out; opos=0;
    }
    n=(int)rd(); m=(int)rd();
    for(int i=0;i<n;i++){ X[i]=rd(); Y[i]=rd(); layer_of[i]=-1; }
    buildLayers();
#ifdef TEST
    // brute reference for comparison (only in test build, ignore for judge)
#endif
    solveQueries();
    if(duck && duck->stdin_ptr){
        duck->stdout_size=opos;
        asm volatile("mov $60,%%rax; xor %%edi,%%edi; syscall" ::: "rax","rdi","memory");
    } else {
        fwrite(obuf,1,opos,stdout);
    }
    return 0;
}

评测结果