代码

// 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<int> upV[MAXK];      // x-increasing upper chain of each layer
static vector<ll> upPref[MAXK];    // prefix cross-sums along upV
static int upLen[MAXK];
static vector<int> delLo[MAXK], delUp[MAXK];  // per-query sorted deleted indices in loV(=vert[0..loLen-1]) / upV
static bool xSafe = false;         // true iff every chain is strictly x-increasing (no vertical edges)
static vector<pair<int,int>> dels;
static vector<int> delByLayer[MAXK];
static int delMark[MAXN];
static int gOrder[MAXN];
static int gPts[MAXN];
static int gInner[MAXN]; static int gInnerCnt=0;
static int delStamp = 0;
static int n, 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); }

// find argmin/argmax of a linear function (crs3 or tval w.r.t. A,B) over layer d's
// two x-monotone chains, via binary search on the unimodal value sequence.
static void extrema(int d, int A, int B, bool useCrs, int& mn, int& mx){
    int hd = h[d], LL = loLen[d];
    const int* V = vert[d].data();
    auto gv = [&](int t){
        int p = V[t];
        return useCrs ? crs3(A,B,p) : tval(A,B,p);
    };
    auto maxOn = [&](int lo,int hi){ int l=lo, r=hi; while(l<r){ int mid=(l+r)>>1; if(gv(mid) < gv(mid+1)) l=mid+1; else r=mid; } int e=(gv(lo)>=gv(hi))?lo:hi; if(gv(l)>gv(e)) e=l; return e; };
    auto minOn = [&](int lo,int hi){ int l=lo, r=hi; while(l<r){ int mid=(l+r)>>1; if(gv(mid) > gv(mid+1)) l=mid+1; else r=mid; } int e=(gv(lo)<=gv(hi))?lo:hi; if(gv(l)<gv(e)) e=l; return e; };
    int M = maxOn(0, LL-1);
    if(LL < hd){ int M2 = maxOn(LL, hd-1); if(gv(M2) > gv(M)) M = M2; }
    int m = minOn(0, LL-1);
    if(LL < hd){ int m2 = minOn(LL, hd-1); if(gv(m2) < gv(m)) m = m2; }
    mn = m; mx = M;
}

// tangent from external point P to layer d (strictly-convex CCW polygon).
// right tangent: cross(P, vert[t], vert[w]) >= 0 for all w != t.
// left tangent : cross(P, vert[t], vert[w]) <= 0 for all w != t.
// Local characterization (exactly one vertex in the non-collinear case): both neighbors lie on the same side.
static int tangentRight(int P, int d){
    int hd = h[d];
    for(int t=0;t<hd;t++){
        int pr=(t-1+hd)%hd, nx=(t+1)%hd;
        if(crsP(P, vert[d][t], vert[d][pr]) >= 0 && crsP(P, vert[d][t], vert[d][nx]) >= 0)
            return t;
    }
    return -1;
}
static int tangentLeft(int P, int d){
    int hd = h[d];
    for(int t=0;t<hd;t++){
        int pr=(t-1+hd)%hd, nx=(t+1)%hd;
        if(crsP(P, vert[d][t], vert[d][pr]) <= 0 && crsP(P, vert[d][t], vert[d][nx]) <= 0)
            return t;
    }
    return -1;
}

// 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, A, B, true, m, M);
    ll gM = g(M), gm = g(m);
    allBelow = false;
    if(gm > 0) return false;   // all above AB
    if(gM < 0){                // all below: exposed arc is delimited by the point-to-chain
                               // tangents from the two anchors A and B (not the t-extremes).
        allBelow = true;
        // If this layer has deletions, the caller will use the exact materialize path
        // (the deletions can expose the next layer's "top" vertices), so skip the tangent scan.
        if(!delByLayer[d].empty()){ fallback = true; return false; }
        int TA = tangentRight(A, d);
        int TB = tangentLeft(B, d);
        if(TA < 0 || TB < 0){ fallback = true; return false; }
        int lenCCW = (TB - TA + hd) % hd + 1;
        if(lenCCW == 1){ s = TA; len = 1; step = +1; return true; }
        {
            ll tTA = tval(A,B,vert[d][TA]);
            ll tTB = tval(A,B,vert[d][TB]);
            ll tB = tval(A,B,B);
            if(tTA < 0 || tTA > tB || tTB < 0 || tTB > tB){ fallback = true; return false; }
            int p0 = vert[d][TA];
            int p1 = vert[d][(TA + 1) % hd];
            int pLm1 = vert[d][(TB - 1 + hd) % hd];
            int pL = vert[d][TB];
            ll d0 = tval(A,B,p1) - tval(A,B,p0);
            ll dL = tval(A,B,pL) - tval(A,B,pLm1);
            if((d0 > 0 && dL < 0) || (d0 < 0 && dL > 0) || d0 == 0 || dL == 0){
                fallback = true; return false;
            }
            if(d0 > 0){ s = TA; step = +1; len = lenCCW; }
            else { s = TB; step = -1; len = lenCCW; }
        }
        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 mergeInPlace(Chain& cur, const Chain& C, int i, int j){
    int idxA = (int)(upper_bound(cur.szPref.begin(), cur.szPref.end(), i) - cur.szPref.begin()) - 1;
    cur.pc.resize(idxA+1);
    cur.pc[idxA].kLen = i - cur.szPref[idxA] + 1;
    int idxB = (int)(upper_bound(C.szPref.begin(), C.szPref.end(), j) - C.szPref.begin()) - 1;
    {
        Piece q = C.pc[idxB];
        q.kStart += (j - C.szPref[idxB]);
        q.kLen -= (j - C.szPref[idxB]);
        if(q.kLen > 0) cur.pc.push_back(q);
    }
    for(int t=idxB+1;t<(int)C.pc.size();t++) cur.pc.push_back(C.pc[t]);
    cur.szPref.clear(); cur.szPref.push_back(0);
    for(auto& p : cur.pc) cur.szPref.push_back(cur.szPref.back() + p.kLen);
    rebuildChainCS(cur);
}

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.
        if(!delByLayer[d].empty()){ 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(int p : delByLayer[d]){
        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);
    }
    if(dp.size()>1){ 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: single-pass materialize + sort + graham. Collects every surviving point
// strictly below the chord AB across all inner layers in ONE pass (O(total below-arc size)),
// instead of recursing once per deleted gap (which re-materializes each deeper layer's
// below-arc and becomes exponential for all-below layers with deletions spread across them).
static vector<int> E;
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, A, B, true, 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){
    for(int d2=d+1; d2<K; d2++){
        int h2 = h[d2];
        if(h2 < 3){
            for(int t=0;t<h2;t++){
                int p = vert[d2][t];
                if(delMark[p] == delStamp) continue;
                if(hval(A,B,p) < 0) E.push_back(p);
            }
            continue;
        }
        int fa,fb;
        int r = findArcFast(A,B,d2,fa,fb);
        if(r == 0) continue;
        if(r == -1){ r = findArcSlow(A,B,d2,fa,fb); if(r == 0) continue; }
        int lo = fa, hi = (fb >= fa) ? fb : fb + h2;
        for(int t=lo; t<=hi; t++){
            int p = vert[d2][t % h2];
            if(delMark[p] != delStamp) E.push_back(p);
        }
    }
}
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;
}

static bool anyCollinearExtreme(int A, int B){
    for(int d=1; d<K; d++){
        int hd = h[d];
        if(hd < 3) continue;
        int tmn, tmx; extrema(d, A, B, false, tmn, tmx);
        int pr=(tmn-1+hd)%hd, nx=(tmn+1)%hd;
        if(tval(A,B,vert[d][pr])==tval(A,B,vert[d][tmn])) return true;
        if(tval(A,B,vert[d][nx])==tval(A,B,vert[d][tmn])) return true;
        pr=(tmx-1+hd)%hd; nx=(tmx+1)%hd;
        if(tval(A,B,vert[d][pr])==tval(A,B,vert[d][tmx])) return true;
        if(tval(A,B,vert[d][nx])==tval(A,B,vert[d][tmx])) return true;
    }
    return false;
}

// true if the outermost inner layer (first with h>=3) is entirely below chord A->B.
static bool innerAllBelow(int A, int B){
    int d0 = 1;
    while(d0 < K && h[d0] < 3) d0++;
    if(d0 >= K) return false;
    int m, M; extrema(d0, A, B, true, m, M);
    return crs3(A,B,vert[d0][M]) < 0;
}

// O(log h) tangent from external point P to convex polygon layer d, kind=+1 right / -1 left.
static int ucArr[MAXN+5];
static int tangentPoly(int P, int d, int kind){
    int hd = h[d], LL = loLen[d];
    int cand[10]; int nc=0;
    auto add=[&](int idx){ for(int i=0;i<nc;i++) if(cand[i]==idx) return; cand[nc++]=idx; };
    auto crsLo=[&](int i, int j){ return crsP(P, vert[d][i], vert[d][j]); };
    if(LL >= 2){
        {int lo=0,hi=LL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsLo(mid,mid+1)<0) lo=mid+1; else hi=mid; } add(lo);}
        {int lo=0,hi=LL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsLo(mid,mid+1)>0) lo=mid+1; else hi=mid; } add(lo);}
    }
    int uL=0; ucArr[uL++]=0;
    for(int i=hd-1;i>=LL;i--) ucArr[uL++]=i;
    if(uL>1 && ucArr[uL-1]!=LL-1) ucArr[uL++]=LL-1;
    if(uL>=2){
        auto crsUp=[&](int i, int j){ return crsP(P, vert[d][ucArr[i]], vert[d][ucArr[j]]); };
        {int lo=0,hi=uL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsUp(mid,mid+1)<0) lo=mid+1; else hi=mid; } add(ucArr[lo]);}
        {int lo=0,hi=uL-1; while(lo<hi){ int mid=(lo+hi)>>1; if(crsUp(mid,mid+1)>0) lo=mid+1; else hi=mid; } add(ucArr[lo]);}
    }
    add(0); add(LL-1);
    int best=-1; ll bestDist=-1;
    auto consider=[&](int t){
        int pr=(t-1+hd)%hd, nx=(t+1)%hd;
        ll a=crsP(P, vert[d][t], vert[d][pr]);
        ll b=crsP(P, vert[d][t], vert[d][nx]);
        bool ok = (kind==+1) ? (a>=0 && b>=0) : (a<=0 && b<=0);
        if(!ok) return;
        ll dd=(X[vert[d][t]]-X[P])*(X[vert[d][t]]-X[P])+(Y[vert[d][t]]-Y[P])*(Y[vert[d][t]]-Y[P]);
        if(dd>bestDist){ bestDist=dd; best=t; }
    };
    for(int i=0;i<nc;i++) consider(cand[i]);
    if(best>=0) return best;
    for(int t=0;t<hd;t++) consider(t);
    return best;
}

static ll arcCS(int d, int a, int b){
    if(a==b) return 0;
    if(a<b) return pref[d][b]-pref[d][a];
    return pref[d][h[d]]-pref[d][a]+pref[d][b];
}

// argmin (wantMin=true) / argmax (wantMin=false) of the polar angle around C over the CCW
// arc [a..b] (unwrapped, b>=a). The polar angle is unimodal on a below-AB arc (a convex
// chain whose supporting chord AB passes through the two anchors), so binary search works.
// This is the robust O(log h) replacement for tangentPoly: it never degrades when C is
// nearly on the layer's boundary (the circle-onion case), because the arc is restricted to
// the strictly-below side of the chord.
static int angleExtreme(int C, int d, int a, int b, bool wantMin){
    int hd = h[d];
    int l=a, r=b;
    auto gt = [&](int i, int j){ return crsP(C, vert[d][i % hd], vert[d][j % hd]) < 0; }; // angle(i) > angle(j)
    if(wantMin){
        while(l<r){ int mid=(l+r)>>1; if(gt(mid, mid+1)) l=mid+1; else r=mid; }
    } else {
        while(l<r){ int mid=(l+r)>>1; if(!gt(mid, mid+1)) l=mid+1; else r=mid; }
    }
    return l % hd;
}

// Point-to-convex-polygon tangents (argmin/argmax polar angle around C over the FULL layer).
// The polar angle around an external C is cyclic bitonic (one peak, one valley). The peak/valley
// are the point-to-layer tangents; each is either an angle extremum on one of the two x-monotone
// chains (found by the unimodal cross-product search below) or one of the two extreme vertices
// (leftmost/rightmost). We gather those O(1) candidates, verify with the O(1) local predicate,
// and only fall back to the correct wrap-safe O(h) scan for degenerate/collinear cases.
static int tangentMono(int P, int d, int ckind, int lo, int hi, bool wantMax); // fwd (defined below)

// O(log) argmax/argmin of the linear function ax*X + ay*Y over layer d's CCW convex polygon.
// Same rotated-array search + verify + O(h) fallback as linearMax/linearMin below, but for an
// arbitrary direction (used by the tangent split below).
static int linearExtremum(int d, ll ax, ll ay, bool wantMax){
    int n = h[d];
    const int* V = vert[d].data();
    auto f = [&](int i){ return ax*X[V[i]] + ay*Y[V[i]]; };
    auto dec = [&](int i){ return f(i) > f((i+1)%n); };
    auto asc = [&](int i){ return f(i) < f((i+1)%n); };
    int lo=0, hi=n-1;
    while(lo<hi){
        int mid=(lo+hi)>>1;
        bool dm = wantMax ? dec(mid) : asc(mid);
        bool dh = wantMax ? dec(hi) : asc(hi);
        if((dm?0:1) > (dh?0:1)) lo=mid+1; else hi=mid;
    }
    int e=lo;
    {
        int pr=(e-1+n)%n, nx=(e+1)%n;
        if(wantMax){ if(f(e) >= f(pr) && f(e) >= f(nx)) return e; }
        else { if(f(e) <= f(pr) && f(e) <= f(nx)) return e; }
    }
    int best=0;
    for(int t=1;t<n;t++) if(wantMax ? (f(t) > f(best)) : (f(t) < f(best))) best=t;
    return best;
}

// O(log) point-to-convex-polygon tangents. The visible arc (edges with g<0) is a single cyclic
// block whose two boundaries are the tangents: cyclicMin = right tangent = `-→+` transition of g,
// cyclicMax = left tangent = `+→-` transition. Split the cycle at the support points in direction
// ±P (argmax/argmin of dot(P,·), found by linearExtremum), binary-search the monotone sign change
// in each half, verify with the O(1) local predicate, and fall back to the O(h) scan only on
// degenerate (collinear/near-boundary) cases (~0 on real data).
static int cyclicMin(int C, int d){ // argmin polar angle = right tangent = `-→+` transition of g
    int hd=h[d];
    auto g=[&](int i){ return crs3(vert[d][i], vert[d][(i+1)%hd], C); };
    auto isRT=[&](int t){ int pr=(t-1+hd)%hd, nx=(t+1)%hd; return crsP(C,vert[d][t],vert[d][pr])>=0 && crsP(C,vert[d][t],vert[d][nx])>=0; };
    int topC = linearExtremum(d, X[C], Y[C], true);
    int botC = linearExtremum(d, X[C], Y[C], false);
    int len=(botC-topC+hd)%hd+1;
    int lo=0, hi=len-1, ans=-1;
    while(lo<=hi){ int mid=(lo+hi)>>1; int t=(topC+mid)%hd; if(g(t)>=0){ ans=mid; hi=mid-1; } else lo=mid+1; }
    if(ans>=0){ int t=(topC+ans)%hd; if(isRT(t)) return t; }
    for(int t=0;t<hd;t++) if(isRT(t)) return t;
    return 0;
}
static int cyclicMax(int C, int d){ // argmax polar angle = left tangent = `+→-` transition of g
    int hd=h[d];
    auto g=[&](int i){ return crs3(vert[d][i], vert[d][(i+1)%hd], C); };
    auto isLT=[&](int t){ int pr=(t-1+hd)%hd, nx=(t+1)%hd; return crsP(C,vert[d][t],vert[d][pr])<=0 && crsP(C,vert[d][t],vert[d][nx])<=0; };
    int topC = linearExtremum(d, X[C], Y[C], true);
    int botC = linearExtremum(d, X[C], Y[C], false);
    int len=(topC-botC+hd)%hd+1;
    int lo=0, hi=len-1, ans=-1;
    while(lo<=hi){ int mid=(lo+hi)>>1; int t=(botC+mid)%hd; if(g(t)<0){ ans=mid; hi=mid-1; } else lo=mid+1; }
    if(ans>=0){ int t=(botC+ans)%hd; if(isLT(t)) return t; }
    for(int t=0;t<hd;t++) if(isLT(t)) return t;
    return 0;
}

// argmax / argmin of the linear function crs3(P,Q,·) over layer d (cyclic bitonic, same
// structure as the polar-angle extrema above). These replace the chain-based `extrema` in the
// hot recursion: the linear function increases to a single peak and decreases to a single
// valley around a convex polygon, so a rotated-array minimum search on the derivative sign
// finds both extrema in O(log h) with far fewer cross products.
static int linearMax(int P, int Q, int d){ // argmax of crs3(P,Q,·)
    int n = h[d];
    ll dx = X[Q]-X[P], dy = Y[Q]-Y[P];
    const int* V = vert[d].data();
    auto g = [&](int i){ return X[V[i]]*dy - Y[V[i]]*dx; };
    auto dec = [&](int i){ return g(i) > g((i+1)%n); };
    int lo=0, hi=n-1;
    while(lo<hi){
        int mid=(lo+hi)>>1;
        if((dec(mid)?0:1) > (dec(hi)?0:1)) lo=mid+1; else hi=mid;
    }
    int peak=lo;
    {
        int pr=(peak-1+n)%n, nx=(peak+1)%n;
        if(g(peak) >= g(pr) && g(peak) >= g(nx))
            return peak;
    }
    int best=0;
    for(int t=1;t<n;t++) if(g(t) > g(best)) best=t;
    return best;
}
static int linearMin(int P, int Q, int d){ // argmin of crs3(P,Q,·)
    int n = h[d];
    ll dx = X[Q]-X[P], dy = Y[Q]-Y[P];
    const int* V = vert[d].data();
    auto g = [&](int i){ return X[V[i]]*dy - Y[V[i]]*dx; };
    auto asc = [&](int i){ return g(i) <= g((i+1)%n); };
    int lo=0, hi=n-1;
    while(lo<hi){
        int mid=(lo+hi)>>1;
        if((asc(mid)?0:1) > (asc(hi)?0:1)) lo=mid+1; else hi=mid;
    }
    int valley=lo;
    {
        int pr=(valley-1+n)%n, nx=(valley+1)%n;
        if(g(valley) <= g(pr) && g(valley) <= g(nx))
            return valley;
    }
    int best=0;
    for(int t=1;t<n;t++) if(g(t) < g(best)) best=t;
    return best;
}

// per-query memo for exposedAreaTangent: its result is a pure function of (d,P,Q) given the
// fixed per-query deletion set, so cache by packed (d,P,Q). Epoch-coded by delStamp (incremented
// per query) so no clearing is needed: a slot with gen != delStamp is empty.
static const int MEMO_SZ = 1<<13;
static struct { ll key; ll area; int gen; } memo[MEMO_SZ];
static inline ll memoKey(int d, int P, int Q){ return ((ll)d << 40) | ((ll)P << 20) | (ll)Q; }
static ll* memoFind(ll key){
    int s = (int)(key & (MEMO_SZ-1));
    for(int t=0;t<MEMO_SZ;t++){
        int i=(s+t)&(MEMO_SZ-1);
        if(memo[i].gen == delStamp){ if(memo[i].key == key) return &memo[i].area; }
        else return nullptr;
    }
    return nullptr;
}
static void memoInsert(ll key, ll area){
    int s = (int)(key & (MEMO_SZ-1));
    for(int t=0;t<MEMO_SZ;t++){
        int i=(s+t)&(MEMO_SZ-1);
        if(memo[i].gen != delStamp){ memo[i].gen=delStamp; memo[i].key=key; memo[i].area=area; return; }
        if(memo[i].key == key){ memo[i].area=area; return; }
    }
}

static ll exposedAreaTangentRaw(int d, int P, int Q, bool& fb);

static ll exposedAreaTangent(int d, int P, int Q, bool& fb){
    ll key = memoKey(d, P, Q);
    ll* hit = memoFind(key);
    if(hit){ fb = false; return *hit; }
    ll r = exposedAreaTangentRaw(d, P, Q, fb);
    if(!fb) memoInsert(key, r);
    return r;
}

// tangent-delimited exposed-chain area from P to Q through surviving allBelow layers d..K-1.
static ll exposedAreaTangentRaw(int d, int P, int Q, bool& fb){
    if(d >= K) return cross2(P, Q);
    int hd = h[d];
    if(hd < 3){
        // Degenerate innermost layer (<=2 surviving leftover points). The exposed chain
        // is the convex hull of {P,Q} + the surviving points below chord P->Q; compute it
        // exactly (at most 4 points) instead of naively concatenating (which wrongly keeps
        // a below point that lies inside the triangle P-Q-other).
        int arr[4]; int ac=0;
        arr[ac++]=P; arr[ac++]=Q;
        for(int t=0;t<hd;t++){ int p=vert[d][t]; if(delMark[p]!=delStamp && crs3(P,Q,p) < 0) arr[ac++]=p; }
        if(ac==2) return exposedAreaTangent(d+1, P, Q, fb);
        if(ac==3) return cross2(P,arr[2])+cross2(arr[2],Q);
        // ac==4: convex hull of {P,Q,a,b}
        for(int i=0;i<ac;i++) for(int j=i+1;j<ac;j++)
            if(X[arr[j]]<X[arr[i]] || (X[arr[j]]==X[arr[i]] && Y[arr[j]]<Y[arr[i]])) swap(arr[i],arr[j]);
        int stk[8]; int top=0;
        for(int i=0;i<ac;i++){ int idx=arr[i]; while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
        int lower=top;
        for(int i=ac-2;i>=0;i--){ int idx=arr[i]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
        top--;
        int iP=-1,iQ=-1;
        for(int i=0;i<top;i++){ if(stk[i]==P)iP=i; if(stk[i]==Q)iQ=i; }
        if(iP<0||iQ<0) return cross2(P,Q);
        ll s=0;
        if(stk[(iP+1)%top]==Q){ for(int k=iP;;k=(k-1+top)%top){ int nxt=(k-1+top)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==Q) break; } }
        else { for(int k=iP;;k=(k+1)%top){ int nxt=(k+1)%top; s+=cross2(stk[k],stk[nxt]); if(stk[nxt]==Q) break; } }
        return s;
    }
    int M = linearMax(P, Q, d);
    ll gM = crs3(P,Q,vert[d][M]);
    int m = 0; ll gm = 0;
    if(gM > 0){
        m = linearMin(P, Q, d);
        gm = crs3(P,Q,vert[d][m]);
        if(gm >= 0) return cross2(P, Q);   // all above chord (or tangent) -> deeper layers also above
    }
    // gm < 0: some point strictly below. Determine the below arc [fa..fb].
    bool allBelow = (gM <= 0);   // gM==0 = tangent touch, still handled by the full-layer tangents
    int fa, fbEnd;
    if(allBelow){ fa = 0; fbEnd = hd - 1; }
    else {
        int lo=M, hi=m; if(hi<lo) hi+=hd;
        while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(P,Q,vert[d][mid%hd])>=0) lo=mid+1; else hi=mid; }
        fa = lo % hd;
        lo=m; hi=M; if(hi<lo) hi+=hd;
        while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(P,Q,vert[d][mid%hd])<0) lo=mid+1; else hi=mid; }
        fbEnd = (lo-1+hd) % hd;
    }
    int TA, TB;
    if(allBelow){
        // whole layer below (or tangent): exposed arc delimited by the point-to-layer tangents,
        // found via the cyclic polar-angle extrema (robust even when P/Q nearly touch the layer).
        TA = cyclicMin(P, d);
        TB = cyclicMax(Q, d);
    } else {
        // intersecting: tangents live inside the below arc; find them by the unimodal polar
        // angle (robust when P/Q are nearly on the layer boundary, as in circle-onion data).
        int a=fa, b=fbEnd; if(b<a) b+=hd;
        TA = angleExtreme(P, d, a, b, true);
        TB = angleExtreme(Q, d, a, b, false);
    }
    int len = (TB - TA + hd) % hd + 1;
    int dpos[130]; int dc=0;
    for(int p : delByLayer[d]){
        int off=(p-TA+hd)%hd;
        if(off<len) dpos[dc++]=off;
    }
    if(dc>1){ sort(dpos, dpos+dc); dc = (int)(unique(dpos, dpos+dc) - dpos); }
    // Deleted tangent vertex -> materialize (rare, but the correct tangent to the surviving
    // arc is not simply the adjacent vertex).
    if(dc>0 && (dpos[0]==0 || dpos[dc-1]==len-1)){ fb=true; return 0; }
    ll area=0;
    {
        int firstSurv=TA;
        if(dc>0 && dpos[0]==0) firstSurv=(TA-1+hd)%hd;
        area += cross2(P, vert[d][firstSurv]);
    }
    int cur=0; int i=0;
    while(i<dc){
        int pk=dpos[i], qk=pk;
        while(i+1<dc && dpos[i+1]==qk+1) qk=dpos[++i];
        if(pk-1>=cur){ int a=(TA+cur)%hd, b=(TA+pk-1)%hd; area+=arcCS(d,a,b); }
        int Pa=(TA+pk-1)%hd; if(Pa<0)Pa+=hd;
        int Qa=(TA+qk+1)%hd;
        area += exposedAreaTangent(d+1, vert[d][Pa], vert[d][Qa], fb);
        if(fb) return 0;
        cur=qk+1; i++;
    }
    if(cur<=len-1){ int a=(TA+cur)%hd; area+=arcCS(d,a,TB); }
    {
        int lastSurv=TB;
        if(dc>0 && dpos[dc-1]==len-1) lastSurv=(TB+1)%hd;
        area += cross2(vert[d][lastSurv], Q);
    }
    return area;
}

// sort-free materialize: collect A,B and surviving f<0 inner points in pre-sorted (x,y)
// order, then Andrew monotone chain. Returns the same value as buildExposed+convexChain.
static ll convexChainSorted(int A, int B){
    bool ab = innerAllBelow(A,B);
    // if allBelow and no inner deletions, the hull is just {A,B} + outermost inner layer
    // (deeper layers are strictly inside and never on the hull).
    int cnt = 0;
    if(ab){
        bool anyInnerDel = false;
        for(int dd=1; dd<K; dd++) if(!delByLayer[dd].empty()){ anyInnerDel = true; break; }
        if(!anyInnerDel){
            gPts[cnt++] = A; gPts[cnt++] = B;
            int d0 = 1; while(d0 < K && h[d0] < 3) d0++;
            if(d0 < K){
                for(int t=0;t<h[d0];t++){
                    int p = vert[d0][t];
                    if(delMark[p] == delStamp) continue;
                    gPts[cnt++] = p;
                }
            }
            sort(gPts, gPts+cnt, [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
            goto hull;
        }
    }
    for(int ii=0; ii<n; ii++){
        int p = gOrder[ii];
        if(p == A || p == B){ gPts[cnt++] = p; continue; }
        if(layer_of[p] < 1) continue;
        if(delMark[p] == delStamp) continue;
        if(!ab && crs3(A,B,p) >= 0) continue;
        gPts[cnt++] = p;
    }
hull:
    if(cnt < 3) return cross2(A,B);
    static int stk[MAXN*2]; int top=0;
    for(int t=0;t<cnt;t++){ int idx=gPts[t]; while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
    int lower=top;
    for(int t=cnt-2;t>=0;t--){ int idx=gPts[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;
}

// ===================== X-monotone fast path =====================
// For a gap (A,B) on L0, the exposed chain is the surviving points strictly below the
// chord A->B (hval<0), which for each inner layer is a contiguous CCW arc (raw below-arc
// for the intersecting case, tangent-delimited for the allBelow case). That arc is walked
// x-INCREASING (a convex x-monotone chain for the general-position judge data) and clipped
// by X-intervals along the ORIGINAL chord, so the recursion visits O(k) nodes per query.
// A.x<B.x -> lower envelope (lowerBridge), A.x>B.x -> upper envelope (upperBridge, negated).

// upper common tangent of two x-increasing UPPER chains (sign-flipped lowerBridge).
static int upperTangentJ(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> upperBridge(const Chain& A, const Chain& B){
    int p = A.size();
    if(p == 1) return {0, upperTangentJ(chainPoint(A,0), B)};
    int lo=0, hi=p-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j = upperTangentJ(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=upperTangentJ(chainPoint(A,i), B);
    return {i,j};
}

// below-AB arc of layer d (h>=3) walked x-increasing: (s,len,step) in vert[d] order.
// step=+1: chain[k]=vert[d][(s+k)%h]; step=-1: vert[d][(s-k+h)%h].
// Returns false if empty (all above AB); fallback set on collinear / non-x-monotone arc.
static bool lowerHullArcX(int d, int A, int B, int& s, int& len, int& step, bool& fallback){
    int hd = h[d];
    auto g = [&](int t){ return hval(A,B,vert[d][t % hd]); };
    int m, M; extrema(d, A, B, true, m, M);
    ll gM = g(M), gm = g(m);
    if(gm > 0) return false;   // all above AB
    int fa, fb;
    if(gM < 0){
        // all below: exposed arc delimited by the point-to-layer tangents from A,B.
        fa = cyclicMin(A, d);
        fb = cyclicMax(B, d);
        if(fa < 0 || fb < 0){ fallback = true; return false; }
    } else if(gM == 0 || gm == 0){
        fallback = true; return false;
    } else {
        // intersecting: below-arc [f0..f1] via the two sign changes of g, then the exposed
        // arc is delimited by the point-to-layer tangents from A,B inside that below-arc.
        int f0, f1;
        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; }
        f0 = 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; }
        f1 = (lo-1+hd) % hd;
        int a=f0, b=f1; if(b<a) b+=hd;
        fa = angleExtreme(A, d, a, b, true);
        fb = angleExtreme(B, d, a, b, false);
    }
    // A deleted tangent vertex shifts the tangent to the surviving arc (not simply the
    // adjacent vertex); that rare case is left to the (correct) tangent/materialize path.
    if(delMark[vert[d][fa]] == delStamp || delMark[vert[d][fb]] == delStamp){ fallback = true; return false; }
    int lenCCW = (fb - fa + hd) % hd + 1;
    // x-monotonicity: the arc must not contain the layer's leftmost(0)/rightmost(loLen-1)
    // as an interior point (otherwise x is bimodal along the CCW arc).
    if(lenCCW > 1){
        int a = fa, b = fa + lenCCW - 1;
        auto interior = [&](int p){ return (a < p && p < b) || (a < p+hd && p+hd < b); };
        if(interior(0) || interior(loLen[d]-1)){ fallback = true; return false; }
    }
    // walk x-increasing
    if(X[vert[d][fa]] <= X[vert[d][fb]]){ s = fa; step = +1; }
    else { s = fb; step = -1; }
    len = lenCCW;
    return true;
}

// enumerate surviving below-AB arcs of layers d.. for chord A,B, clipped to x in [xL,xR],
// x-increasing. Recurse on the ORIGINAL chord with x-intervals (non-exponential).
static void collectArcsX(int d, int A, int B, ll xL, ll xR, vector<Piece>& out, bool& fallback){
    if(d >= K) return;
    int hd = h[d];
    if(hd < 3){
        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 xv = X[p];
                if(xv >= xL && xv <= xR) tmp[cnt++] = p;
            }
        }
        if(cnt == 2 && X[tmp[0]] > X[tmp[1]]) 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;
    if(!lowerHullArcX(d, A, B, s, len, step, fallback)) return;
    // clip to [xL,xR] (x increasing in k)
    int klo = len, khi = -1;
    {
        int l=0, r=len-1;
        while(l<=r){ int mid=(l+r)>>1; if(X[arcPoint(d,s,step,mid)] >= xL){ klo=mid; r=mid-1; } else l=mid+1; }
        l=0; r=len-1;
        while(l<=r){ int mid=(l+r)>>1; if(X[arcPoint(d,s,step,mid)] <= xR){ khi=mid; l=mid+1; } else r=mid-1; }
    }
    if(klo > khi) return;
    int sllen = khi - klo + 1;
    vector<int> dp;
    for(int p : delByLayer[d]){
        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);
    }
    if(dp.size()>1){ 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];
        if(pk-1 >= cur){
            out.push_back({d, (s + (klo+cur)*step % hd + hd) % hd, step, 0, pk - cur});
        }
        ll xL2 = (pk > 0) ? X[arcPoint(d,s,step,klo+pk-1)] : xL;
        ll xR2 = (qk+1 < sllen) ? X[arcPoint(d,s,step,klo+qk+1)] : xR;
        collectArcsX(d+1, A, B, xL2, xR2, 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});
    }
}

// exposed-chain area for a gap (A,B) via x-monotone arcs. Assumes A.x != B.x.
static bool xExposedArea(int A, int B, ll& res){
    static vector<Piece> arcs;
    arcs.clear();
    bool fallback = false;
    if(X[A] < X[B]){
        collectArcsX(1, A, B, X[A], X[B], arcs, fallback);
        if(fallback) return false;
        static Chain cur, C, Bc;
        chainFromPoint(A, cur);
        for(auto& p : arcs){
            chainFromArc(p.d, p.s, p.kLen, p.step, C);
            auto pr = lowerBridge(cur, C);
            mergeInPlace(cur, C, pr.first, pr.second);
        }
        chainFromPoint(B, Bc);
        auto pr = lowerBridge(cur, Bc);
        mergeInPlace(cur, Bc, pr.first, pr.second);
        res = cur.total();
        return true;
    } else {
        collectArcsX(1, A, B, X[B], X[A], arcs, fallback);
        if(fallback) return false;
        static Chain cur, C, Bc;
        chainFromPoint(B, cur);
        for(auto& p : arcs){
            chainFromArc(p.d, p.s, p.kLen, p.step, C);
            auto pr = upperBridge(cur, C);
            mergeInPlace(cur, C, pr.first, pr.second);
        }
        chainFromPoint(A, Bc);
        auto pr = upperBridge(cur, Bc);
        mergeInPlace(cur, Bc, pr.first, pr.second);
        res = -(cur.total());
        return true;
    }
}
// ===================== straddle: x-bimodal below-arc via two x-monotone halves =====================
// A straddle gap has the exposed chain x-bimodal: it goes from the left anchor, increases to an
// x-extreme of the below-region, then decreases to the right anchor (or vice-versa). The below-arc
// of each layer is tangent-delimited (cyclicMin/cyclicMax for allBelow, angleExtreme for
// intersecting), and is split at the layer's leftmost/rightmost into a lower-chain piece (x inc)
// and an upper-chain piece (x inc). Each piece's area is a prefix-sum; pieces across consecutive
// layers are merged with the lower/upper bridge (never materializing points). Non-exponential: the
// recursion descends only into deleted gaps, clipped by disjoint x-intervals.
struct SPiece { int d; int kind; int s; int len; }; // kind 0=vert[d] (lower, x inc), 1=upV[d] (x inc)
struct SChain {
    vector<SPiece> pc;
    vector<int> szPref;
    vector<ll> csPref;
    int size() const { return szPref.empty() ? 0 : szPref.back(); }
    ll total() const { return csPref.empty() ? 0 : csPref.back(); }
};
static inline int sPoint(const SPiece& p, int k){ return (p.kind==0) ? vert[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int sFirst(const SPiece& p){ return sPoint(p,0); }
static inline int sLast(const SPiece& p){ return sPoint(p,p.len-1); }
static ll sCS(const SPiece& p){
    if(p.len<=1) return 0;
    if(p.kind==0) return pref[p.d][p.s+p.len-1] - pref[p.d][p.s];
    return upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s];
}
static int sChainPoint(const SChain& c, int k){
    int idx=(int)(upper_bound(c.szPref.begin(),c.szPref.end(),k)-c.szPref.begin())-1;
    return sPoint(c.pc[idx], k-c.szPref[idx]);
}
static void sRebuild(SChain& 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(sLast(c.pc[i-1]), sFirst(c.pc[i]));
        v+=sCS(c.pc[i]);
        c.csPref[i+1]=c.csPref[i]+v;
    }
}
static void sFromPoint(int p, SChain& c){
    c.pc.clear(); c.szPref.clear(); c.csPref.clear();
    c.pc.push_back({layer_of[p], 0, pos_of[p], 1});
    c.szPref.push_back(0); c.szPref.push_back(1);
    sRebuild(c);
}
static void sFromPiece(const SPiece& p, SChain& c){
    c.pc.clear(); c.szPref.clear(); c.csPref.clear();
    if(p.len<=0){ sRebuild(c); return; }
    c.pc.push_back(p);
    c.szPref.push_back(0); c.szPref.push_back(p.len);
    sRebuild(c);
}
static int sLowerTangentJ(int oi, const SChain& B){
    int q=B.size(); int lo=0,hi=q-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,sChainPoint(B,mid),sChainPoint(B,mid+1))<0) lo=mid+1; else hi=mid; }
    return lo;
}
// O(log |A|) reversed tangent from point P (right of A) to SChain A: two-level binary search.
static int sRevTangentLower(const SChain& A, int P){
    int m=(int)A.pc.size(), sz=A.size();
    if(sz==1) return 0;
    int t=-1;
    if(m>=2){
        int lo=0,hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sLast(A.pc[mid]), sFirst(A.pc[mid+1]), P)<0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t>=0){
        const SPiece& q=A.pc[t]; int L=q.len; int r=-1;
        if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)<0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r>=0) return A.szPref[t]+r;
        return A.szPref[t]+L-1;
    } else {
        const SPiece& q=A.pc[m-1]; int L=q.len; int r=-1;
        if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)<0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r>=0) return A.szPref[m-1]+r;
        return sz-1;
    }
}
static int sRevTangentUpper(const SChain& A, int P){
    int m=(int)A.pc.size(), sz=A.size();
    if(sz==1) return 0;
    int t=-1;
    if(m>=2){
        int lo=0,hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sLast(A.pc[mid]), sFirst(A.pc[mid+1]), P)>0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t>=0){
        const SPiece& q=A.pc[t]; int L=q.len; int r=-1;
        if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)>0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r>=0) return A.szPref[t]+r;
        return A.szPref[t]+L-1;
    } else {
        const SPiece& q=A.pc[m-1]; int L=q.len; int r=-1;
        if(L>=2){ int lo=0,hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(sPoint(q,mid), sPoint(q,mid+1), P)>0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r>=0) return A.szPref[m-1]+r;
        return sz-1;
    }
}
static pair<int,int> sLowerBridge(const SChain& A, const SChain& B){
    int p=A.size();
    if(p==1) return {0, sLowerTangentJ(sChainPoint(A,0),B)};
    if(B.size()==1) return {sRevTangentLower(A, sChainPoint(B,0)), 0};
    int ci=0, cj=0;
    for(int it=0; it<64; it++){
        int jn=sLowerTangentJ(sChainPoint(A,ci),B);
        int in=sRevTangentLower(A, sChainPoint(B,jn));
        if(in==ci && jn==cj) return {in,jn};
        ci=in; cj=jn;
    }
    int lo=0,hi=p-1,ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j=sLowerTangentJ(sChainPoint(A,mid),B);
        bool ok=(mid==0)||(crs3(sChainPoint(A,mid-1),sChainPoint(A,mid),sChainPoint(B,j))>0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    int i=ans, j=sLowerTangentJ(sChainPoint(A,i),B);
    return {i,j};
}
static int sUpperTangentJ(int oi, const SChain& B){
    int q=B.size(); int lo=0,hi=q-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,sChainPoint(B,mid),sChainPoint(B,mid+1))>0) lo=mid+1; else hi=mid; }
    return lo;
}
static pair<int,int> sUpperBridge(const SChain& A, const SChain& B){
    int p=A.size();
    if(p==1) return {0, sUpperTangentJ(sChainPoint(A,0),B)};
    if(B.size()==1) return {sRevTangentUpper(A, sChainPoint(B,0)), 0};
    int ci=0, cj=0;
    for(int it=0; it<64; it++){
        int jn=sUpperTangentJ(sChainPoint(A,ci),B);
        int in=sRevTangentUpper(A, sChainPoint(B,jn));
        if(in==ci && jn==cj) return {in,jn};
        ci=in; cj=jn;
    }
    int lo=0,hi=p-1,ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j=sUpperTangentJ(sChainPoint(A,mid),B);
        bool ok=(mid==0)||(crs3(sChainPoint(A,mid-1),sChainPoint(A,mid),sChainPoint(B,j))<0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    int i=ans, j=sUpperTangentJ(sChainPoint(A,i),B);
    return {i,j};
}
static void sMerge(SChain& cur, const SChain& C, int i, int j){
    int idxA=(int)(upper_bound(cur.szPref.begin(),cur.szPref.end(),i)-cur.szPref.begin())-1;
    cur.pc.resize(idxA+1);
    cur.pc[idxA].len = i - cur.szPref[idxA] + 1;
    int idxB=(int)(upper_bound(C.szPref.begin(),C.szPref.end(),j)-C.szPref.begin())-1;
    { SPiece q=C.pc[idxB]; q.s+=(j-C.szPref[idxB]); q.len-=(j-C.szPref[idxB]); if(q.len>0) cur.pc.push_back(q); }
    for(int t=idxB+1;t<(int)C.pc.size();t++) cur.pc.push_back(C.pc[t]);
    cur.szPref.clear(); cur.szPref.push_back(0);
    for(auto& p:cur.pc) cur.szPref.push_back(cur.szPref.back()+p.len);
    sRebuild(cur);
}

// upV index of a vert position p (upper-chain point or the two extremes).
static inline int upIdxOfD(int d, int p){ return (p==0) ? 0 : h[d]-p; }

// Tangent-delimited below-arc of layer d w.r.t. chord A->B. Returns TA,TB (vert indices) and the
// wrap flags (strictly interior leftmost/rightmost). Mirrors exposedAreaTangentRaw's arc logic.
static bool belowArcTangents(int d, int A, int B, int& TA, int& TB, bool& wrapR, bool& wrapL){
    int hd=h[d];
    int M=linearMax(A,B,d);
    ll gM=crs3(A,B,vert[d][M]);
    int m=0; ll gm=0;
    if(gM>0){
        m=linearMin(A,B,d);
        gm=crs3(A,B,vert[d][m]);
        if(gm>=0) return false;  // all above chord
    }
    bool allBelow=(gM<=0);
    if(allBelow){
        TA=cyclicMin(A,d);
        TB=cyclicMax(B,d);
    } else {
        int lo=M, hi=m; if(hi<lo) hi+=hd;
        while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(A,B,vert[d][mid%hd])>=0) lo=mid+1; else hi=mid; }
        int fa=lo%hd;
        lo=m; hi=M; if(hi<lo) hi+=hd;
        while(lo<hi){ int mid=(lo+hi)>>1; if(crs3(A,B,vert[d][mid%hd])<0) lo=mid+1; else hi=mid; }
        int fbEnd=(lo-1+hd)%hd;
        int a=fa, b=fbEnd; if(b<a) b+=hd;
        TA=angleExtreme(A,d,a,b,true);
        TB=angleExtreme(B,d,a,b,false);
    }
    int lenCCW=(TB-TA+hd)%hd+1;
    int a=TA, b=a+lenCCW-1;
    wrapR=(a<loLen[d]-1)&&(b>loLen[d]-1);
    wrapL=(a>0)&&(b>hd);
    return true;
}
// lower-chain portion of the below-arc (vert[d] arc, x increasing). Empty => the arc lives on the
// upper chain (only possible when x-monotone).
static bool loPieceRange(int d, int TA, int TB, bool wrapR, bool wrapL, int& s, int& len){
    int LL=loLen[d];
    if(wrapR){ s=TA; len=LL-TA; return len>0; }
    if(wrapL){ s=0; len=TB+1; return len>0; }
    if(TA<=TB && TB<=LL-1){ s=TA; len=TB-TA+1; return true; }
    return false;
}
static bool upPieceRange(int d, int TA, int TB, bool wrapR, bool wrapL, int& s, int& len){
    int hd=h[d], uL=upLen[d];
    if(wrapR){ s=upIdxOfD(d,TB); len=uL-s; return len>0; }
    if(wrapL){ s=0; len=upIdxOfD(d,TA)+1; return len>0; }
    if(TA>=loLen[d] && TB>=loLen[d] && TA<=TB){ int a=upIdxOfD(d,TA), b=upIdxOfD(d,TB); s=b; len=a-b+1; return len>0; }
    return false;
}

// emit pieces of layer d's below-arc for the lower (kind=0) or upper (kind=1) hull, x-clipped to
// [xL,xR], recursing into deleted gaps. Each below-arc is split into a lower-chain piece and an
// upper-chain piece; the ALIGNED piece contributes its full sub-chains (with interior deletion
// recursion), the NON-ALIGNED piece contributes only its first/last surviving points (its x-extremes,
// which matter when the shared leftmost/rightmost is deleted). fallback=true only for the rare
// x-monotone-on-the-other-chain case.
static int sdpos[130];
static bool gXmono = false;   // true: x-monotone single-chain mode (no fallback on the other chain)
static int gD0 = -1, gTA0 = -1, gTB0 = -1;   // precomputed tangents of the outermost inner layer

// unimodal polar-angle tangent from external point P to an x-monotone chain (ckind 0=vert lower,
// 1=upV upper), indices [lo..hi] x-increasing. wantMax = argmax angle (left tangent), else argmin.
static int tangentMono(int P, int d, int ckind, int lo, int hi, bool wantMax){
    int l=lo, r=hi;
    while(l<r){
        int mid=(l+r)>>1;
        int a=(ckind==0)?vert[d][mid]:upV[d][mid];
        int b=(ckind==0)?vert[d][mid+1]:upV[d][mid+1];
        ll c=crsP(P,a,b);   // >0: angle(b) > angle(a)
        if(wantMax){ if(c>0) l=mid+1; else r=mid; }
        else { if(c<0) l=mid+1; else r=mid; }
    }
    return l;
}

static void emitChainPieces(int d, int kind, int A, int B, ll xL, ll xR, vector<SPiece>& out, bool& fallback){
    if(d<0 || d>=K) return;
    int hd=h[d];
    if(hd<3){
        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 xv=X[p]; if(xv>=xL && xv<=xR) tmp[cnt++]=p; }
        }
        if(cnt==2 && X[tmp[0]]>X[tmp[1]]) swap(tmp[0],tmp[1]);
        for(int t=0;t<cnt;t++) out.push_back({layer_of[tmp[t]],0,pos_of[tmp[t]],1});
        return;
    }
    int TA,TB; bool wrapR,wrapL;
    if(gXmono && d==gD0){
        TA=gTA0; TB=gTB0;
        int lenCCW = (TB - TA + hd) % hd + 1;
        int a=TA, b=a+lenCCW-1;
        wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
        wrapL = (a > 0) && (b > hd);
    } else if(gXmono){
        // Fast x-monotone allBelow: skip the gM check and use the unimodal binary search on the
        // single x-monotone chain (no wrap issues, cheaper than the cyclic tangent search).
        if(kind==0){
            TA = tangentMono(A,d,0,0,loLen[d]-1,false);
            TB = tangentMono(B,d,0,0,loLen[d]-1,true);
        } else {
            int ja = tangentMono(A,d,1,0,upLen[d]-1,false);
            int jb = tangentMono(B,d,1,0,upLen[d]-1,true);
            TA = (ja==0) ? 0 : hd-ja;
            TB = (jb==0) ? 0 : hd-jb;
        }
        int lenCCW = (TB - TA + hd) % hd + 1;
        int a=TA, b=a+lenCCW-1;
        wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
        wrapL = (a > 0) && (b > hd);
    } else {
        if(!belowArcTangents(d,A,B,TA,TB,wrapR,wrapL)) return;
    }
    if(delMark[vert[d][TA]]==delStamp || delMark[vert[d][TB]]==delStamp){ fallback=true; return; }
    // The below-arc's shared extreme (leftmost/rightmost) is the below-region's x-extreme; when it
    // is deleted the extreme shifts to the OTHER chain (non-aligned case) -> fall back (correct, rare).
    if(wrapR && delMark[vert[d][loLen[d]-1]]==delStamp){ fallback=true; return; }
    if(wrapL && delMark[vert[d][0]]==delStamp){ fallback=true; return; }
    int s,len;
    if(kind==0){ if(!loPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
    else { if(!upPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
    int i=len, j=-1;
    {
        int lo=0, hi=len-1;
        while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]>=xL){ i=mid; hi=mid-1; } else lo=mid+1; }
        lo=0; hi=len-1;
        while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]<=xR){ j=mid; lo=mid+1; } else hi=mid-1; }
    }
    if(i>j) return;
    const vector<int>& dl=(kind==0)?delByLayer[d]:delUp[d];
    int dc=0;
    {
        int lo=0, hi=(int)dl.size()-1, fst=(int)dl.size();
        while(lo<=hi){ int mid=(lo+hi)>>1; if(dl[mid]>=s+i){ fst=mid; hi=mid-1; } else lo=mid+1; }
        for(int t=fst; t<(int)dl.size() && dl[t]<=s+j; t++) sdpos[dc++]=dl[t]-s;
    }
    int nextD=d+1;
    int cur=0, ii=0;
    while(ii<dc){
        int pk=sdpos[ii], qk=pk;
        while(ii+1<dc && sdpos[ii+1]==qk+1) qk=sdpos[++ii];
        if(pk-1>=cur) out.push_back({d,kind,s+cur,pk-cur});
        ll xL2=(pk>0)?X[(kind==0)?vert[d][s+pk-1]:upV[d][s+pk-1]]:xL;
        ll xR2=(qk+1<len)?X[(kind==0)?vert[d][s+qk+1]:upV[d][s+qk+1]]:xR;
        emitChainPieces(nextD,kind,A,B,xL2,xR2,out,fallback);
        if(fallback) return;
        cur=qk+1; ii++;
    }
    if(cur<=j) out.push_back({d,kind,s+cur,j-cur+1});
}

// Exposed-chain area for a gap (A,B). wR: below-region wraps right (bimodal); wL: wraps left
// (bimodal); neither: x-monotone single-chain. Each below-arc is tangent-delimited and split into
// a lower-chain piece and an upper-chain piece; prefix sums + lower/upper bridge, never materializing.
static bool straddleExposedArea(int A, int B, bool wR, bool wL, ll& res){
    static vector<SPiece> out;
    static SChain cur, C;
    bool fallback=false;
    const ll NEG=-(1LL<<60), POS=(1LL<<60);
    int la = (X[A]<=X[B]) ? A : B;   // left anchor (smaller x)
    int ha = (X[A]<=X[B]) ? B : A;   // right anchor
    // ---- lower hull (x increasing) ----
    out.clear();
    if(wR){ sFromPoint(la, cur); sFromPoint(ha, C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
    else if(wL){ cur.pc.clear(); cur.szPref.clear(); cur.csPref.clear(); }
    else { sFromPoint(la, cur); }   // x-monotone: left anchor at start
    emitChainPieces(1, 0, A, B, NEG, POS, out, fallback);
    if(fallback) return false;
    for(auto& p:out){
        if(cur.size()==0){ sFromPiece(p,cur); }
        else { sFromPiece(p,C); auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
    }
    if(wL){
        if(cur.size()==0){ sFromPoint(la,cur); sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
        else { sFromPoint(la,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
    } else if(!wR){ // x-monotone: right anchor at end
        sFromPoint(ha,C); { auto pr=sLowerBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
    }
    ll lowerSum=cur.total();
    // ---- upper hull (x increasing) ----
    out.clear();
    if(wR){ sFromPoint(la, cur); sFromPoint(ha, C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
    else if(wL){ cur.pc.clear(); cur.szPref.clear(); cur.csPref.clear(); }
    else { sFromPoint(la, cur); }
    emitChainPieces(1, 1, A, B, NEG, POS, out, fallback);
    if(fallback) return false;
    for(auto& p:out){
        if(cur.size()==0){ sFromPiece(p,cur); }
        else { sFromPiece(p,C); auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
    }
    if(wL){
        if(cur.size()==0){ sFromPoint(la,cur); sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
        else { sFromPoint(la,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); } }
    } else if(!wR){
        sFromPoint(ha,C); { auto pr=sUpperBridge(cur,C); sMerge(cur,C,pr.first,pr.second); }
    }
    ll upperSum=cur.total();
    res=lowerSum-upperSum-cross2(B,A);   // signed chain A->...->B (full hull minus closing chord)
    return true;
}

// ---- inline running-hull bridge/merge (NO vectors) for the x-monotone handler ----
// The accumulated x-increasing hull is kept in fixed arrays: spcArr (pieces), spcSz (prefix
// sizes), spcCs (prefix cross-sums). Each merge updates the running cross-sum in O(1) amortized
// via prefix-sum lookups (pieceCS) + the single bridge edge, instead of rebuilding the whole
// csPref vector after every merge (the O(np)-per-merge sRebuild that dominated test 16's constant).
static const int MAXSP = 1024;
static SPiece spcArr[MAXSP];
static int spcSz[MAXSP+1];
static ll spcCs[MAXSP+1];
static int spcN;
static inline int spPoint(const SPiece& p, int k){ return (p.kind==0) ? vert[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int spFirst(const SPiece& p){ return spPoint(p,0); }
static inline int spLast(const SPiece& p){ return spPoint(p,p.len-1); }
static inline ll spCS(const SPiece& p){
    if(p.len<=1) return 0;
    if(p.kind==0) return pref[p.d][p.s+p.len-1] - pref[p.d][p.s];
    return upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s];
}
static inline int hPoint(int k){   // k-th point of the running hull (O(log np))
    int lo=0, hi=spcN;
    while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= k) lo=mid+1; else hi=mid; }
    int idx=lo-1;
    return spPoint(spcArr[idx], k - spcSz[idx]);
}
static int spLowerTangentJ(int oi, const SPiece& p){
    int lo=0, hi=p.len-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) < 0) lo=mid+1; else hi=mid; }
    return lo;
}
static int spUpperTangentJ(int oi, const SPiece& p){
    int lo=0, hi=p.len-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) > 0) lo=mid+1; else hi=mid; }
    return lo;
}
// O(log sz) reversed tangent from point P (to the RIGHT of the running hull) to the running hull:
// returns index i such that all hull points lie above (lower) / below (upper) the line hull[i]->P.
// Two-level binary search (piece level + within piece) — the "straddle" predicate is monotone along
// the weakly-convex x-increasing chain, so O(log np + log piece_len) = O(log sz) with O(1) point access.
static int spRevTangentLower(int P){
    int m = spcN, sz = spcSz[spcN];
    if(sz == 1) return 0;
    int t = -1;
    if(m >= 2){
        int lo=0, hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) < 0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t >= 0){
        const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[t] + r;
        return spcSz[t] + L - 1;
    } else {
        const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[m-1] + r;
        return sz - 1;
    }
}
static int spRevTangentUpper(int P){
    int m = spcN, sz = spcSz[spcN];
    if(sz == 1) return 0;
    int t = -1;
    if(m >= 2){
        int lo=0, hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) > 0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t >= 0){
        const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[t] + r;
        return spcSz[t] + L - 1;
    } else {
        const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[m-1] + r;
        return sz - 1;
    }
}

// O(log |A| + log |B|) lower/upper common tangent via alternating fixpoint of the two point-to-chain
// tangents (both index functions are monotone, so it converges in <=~4 rounds in practice). Falls back
// to the O(log^2) nested search on the (never-observed) slow-convergence path.
static void spLowerBridge(const SPiece& p, int& i, int& j){
    int sz = spcSz[spcN];
    if(sz == 1){ i = 0; j = spLowerTangentJ(hPoint(0), p); return; }
    if(p.len == 1){ i = spRevTangentLower(spPoint(p,0)); j = 0; return; }
    int ci = 0, cj = 0;
    for(int it=0; it<64; it++){
        int jn = spLowerTangentJ(hPoint(ci), p);
        int in = spRevTangentLower(spPoint(p, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo=0, hi=sz-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int jj = spLowerTangentJ(hPoint(mid), p);
        bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) > 0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    i = ans; j = spLowerTangentJ(hPoint(i), p);
}
static void spUpperBridge(const SPiece& p, int& i, int& j){
    int sz = spcSz[spcN];
    if(sz == 1){ i = 0; j = spUpperTangentJ(hPoint(0), p); return; }
    if(p.len == 1){ i = spRevTangentUpper(spPoint(p,0)); j = 0; return; }
    int ci = 0, cj = 0;
    for(int it=0; it<64; it++){
        int jn = spUpperTangentJ(hPoint(ci), p);
        int in = spRevTangentUpper(spPoint(p, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo=0, hi=sz-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int jj = spUpperTangentJ(hPoint(mid), p);
        bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) < 0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    i = ans; j = spUpperTangentJ(hPoint(i), p);
}
// truncate the running hull at global index i, then append piece p's suffix p[j..end].
// cross-sum is updated in O(1) amortized: prefix up to i stays valid, only the tail edge + piece
// suffix are added (no full recompute).
static void spAppend(const SPiece& p, int i, int j){
    int idxA = 0;
    { int lo=0, hi=spcN; while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= i) lo=mid+1; else hi=mid; } idxA = lo-1; }
    spcArr[idxA].len = i - spcSz[idxA] + 1;
    spcN = idxA + 1;
    spcSz[idxA+1] = i + 1;
    spcCs[idxA+1] = spcCs[idxA] + (idxA>0 ? cross2(spLast(spcArr[idxA-1]), spFirst(spcArr[idxA])) : 0) + spCS(spcArr[idxA]);
    SPiece q = p; q.s += j; q.len -= j;
    if(q.len > 0){
        spcArr[spcN] = q;
        spcSz[spcN+1] = spcSz[spcN] + q.len;
        spcCs[spcN+1] = spcCs[spcN] + cross2(spLast(spcArr[spcN-1]), spFirst(q)) + spCS(q);
        spcN++;
    }
}
static void mergeIntoHull(const SPiece& p, int kind){
    int i, j;
    if(kind==0) spLowerBridge(p, i, j); else spUpperBridge(p, i, j);
    spAppend(p, i, j);
}

// emitChainPieces with inline merge into the running hull (no `out` vector materialization).
// Piece order and recursion are IDENTICAL to emitChainPieces; each piece is bridged into the
// accumulated x-monotone hull the moment it is produced (pieces arrive x-increasing).
static void emitChainPiecesMerge(int d, int kind, int A, int B, ll xL, ll xR, bool& fallback){
    if(d<0 || d>=K) return;
    int hd=h[d];
    if(hd<3){
        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 xv=X[p]; if(xv>=xL && xv<=xR) tmp[cnt++]=p; }
        }
        if(cnt==2 && X[tmp[0]]>X[tmp[1]]) swap(tmp[0],tmp[1]);
        for(int t=0;t<cnt;t++){ SPiece pp={layer_of[tmp[t]],0,pos_of[tmp[t]],1}; mergeIntoHull(pp,kind); }
        return;
    }
    int TA,TB; bool wrapR,wrapL;
    if(gXmono && d==gD0){
        TA=gTA0; TB=gTB0;
        int lenCCW = (TB - TA + hd) % hd + 1;
        int a=TA, b=a+lenCCW-1;
        wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
        wrapL = (a > 0) && (b > hd);
    } else if(gXmono){
        if(kind==0){
            TA = tangentMono(A,d,0,0,loLen[d]-1,false);
            TB = tangentMono(B,d,0,0,loLen[d]-1,true);
        } else {
            int ja = tangentMono(A,d,1,0,upLen[d]-1,false);
            int jb = tangentMono(B,d,1,0,upLen[d]-1,true);
            TA = (ja==0) ? 0 : hd-ja;
            TB = (jb==0) ? 0 : hd-jb;
        }
        int lenCCW = (TB - TA + hd) % hd + 1;
        int a=TA, b=a+lenCCW-1;
        wrapR = (a < loLen[d]-1) && (b > loLen[d]-1);
        wrapL = (a > 0) && (b > hd);
    } else {
        if(!belowArcTangents(d,A,B,TA,TB,wrapR,wrapL)) return;
    }
    if(delMark[vert[d][TA]]==delStamp || delMark[vert[d][TB]]==delStamp){ fallback=true; return; }
    if(wrapR && delMark[vert[d][loLen[d]-1]]==delStamp){ fallback=true; return; }
    if(wrapL && delMark[vert[d][0]]==delStamp){ fallback=true; return; }
    int s,len;
    if(kind==0){ if(!loPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
    else { if(!upPieceRange(d,TA,TB,wrapR,wrapL,s,len)){ if(gXmono || wrapR || wrapL) return; fallback=true; return; } }
    int i=len, j=-1;
    {
        int lo=0, hi=len-1;
        while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]>=xL){ i=mid; hi=mid-1; } else lo=mid+1; }
        lo=0; hi=len-1;
        while(lo<=hi){ int mid=(lo+hi)>>1; int p=(kind==0)?vert[d][s+mid]:upV[d][s+mid]; if(X[p]<=xR){ j=mid; lo=mid+1; } else hi=mid-1; }
    }
    if(i>j) return;
    const vector<int>& dl=(kind==0)?delByLayer[d]:delUp[d];
    int dc=0;
    {
        int lo=0, hi=(int)dl.size()-1, fst=(int)dl.size();
        while(lo<=hi){ int mid=(lo+hi)>>1; if(dl[mid]>=s+i){ fst=mid; hi=mid-1; } else lo=mid+1; }
        for(int t=fst; t<(int)dl.size() && dl[t]<=s+j; t++) sdpos[dc++]=dl[t]-s;
    }
    int nextD=d+1;
    int cur=0, ii=0;
    while(ii<dc){
        int pk=sdpos[ii], qk=pk;
        while(ii+1<dc && sdpos[ii+1]==qk+1) qk=sdpos[++ii];
        if(pk-1>=cur){ SPiece pp={d,kind,s+cur,pk-cur}; mergeIntoHull(pp,kind); }
        ll xL2=(pk>0)?X[(kind==0)?vert[d][s+pk-1]:upV[d][s+pk-1]]:xL;
        ll xR2=(qk+1<len)?X[(kind==0)?vert[d][s+qk+1]:upV[d][s+qk+1]]:xR;
        emitChainPiecesMerge(nextD,kind,A,B,xL2,xR2,fallback);
        if(fallback) return;
        cur=qk+1; ii++;
    }
    if(cur<=j){ SPiece pp={d,kind,s+cur,j-cur+1}; mergeIntoHull(pp,kind); }
}

// x-monotone single-chain exposed area (test 16's case): the below-arc is tangent-delimited and
// strictly x-monotone on one chain (lower or upper), so the tangent search is unimodal with no wrap.
// Build the one x-increasing chain [left-anchor] + pieces + [right-anchor] with prefix sums + bridge,
// merging each piece into a running fixed-array hull (no vector materialization anywhere).
static bool xmonotoneExposedArea(int A, int B, int d0, int TA, int TB, ll& res){
    bool fallback=false;
    const ll NEG=-(1LL<<60), POS=(1LL<<60);
    int la = (X[A]<=X[B]) ? A : B;
    int ha = (X[A]<=X[B]) ? B : A;
    if(TA==TB) return false;   // degenerate
    // The exposed chain A->TA->arc->TB->B is x-monotone ONLY if the tangent-delimited arc's
    // x-range lies strictly between the two anchors (otherwise the tangent edges wrap and the
    // chain is bimodal, handled by straddleExposedArea).
    {
        ll xlo=X[vert[d0][TA]], xhi=X[vert[d0][TB]];
        if(xlo>xhi){ ll t=xlo; xlo=xhi; xhi=t; }
        if(!(X[la] < xlo && X[ha] > xhi)) return false;
    }
    int s,len,kind;
    bool wR=false,wL=false;
    if(loPieceRange(d0,TA,TB,wR,wL,s,len)) kind=0;
    else if(upPieceRange(d0,TA,TB,wR,wL,s,len)) kind=1;
    else return false;
    spcArr[0] = {0, 0, pos_of[la], 1};
    spcSz[0] = 0; spcSz[1] = 1;
    spcCs[0] = 0; spcCs[1] = 0;
    spcN = 1;
    gXmono = true; gD0=d0; gTA0=TA; gTB0=TB;
    emitChainPiecesMerge(1, kind, A, B, NEG, POS, fallback);
    gXmono = false;
    if(fallback) return false;
    { SPiece q={0,0,pos_of[ha],1}; mergeIntoHull(q, kind); }
    ll crossSum=spcCs[spcN];
    res=(X[A]<=X[B])?crossSum:-crossSum;
    return true;
}

// 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 tB = tval(A,B,B);
    // Primary fast path: collectArcs + lowerBridge (original chord + t-clip, non-exponential).
    // Fast and correct for the t-monotone deep-onion tests (5-19).
    static vector<Piece> arcs;
    arcs.clear();
    bool fallback = false;
    collectArcs(1, A, B, 0, tB, arcs, fallback);
    if(!fallback){
        static Chain cur, C, Bc;
        chainFromPoint(A, cur);
        for(auto& p : arcs){
            chainFromArc(p.d, p.s, p.kLen, p.step, C);
            auto [i,j] = lowerBridge(cur, C);
            mergeInPlace(cur, C, i, j);
        }
        chainFromPoint(B, Bc);
        auto [i,j] = lowerBridge(cur, Bc);
        mergeInPlace(cur, Bc, i, j);
        return cur.total();
    }
    // Fallback: try the x-bimodal tangent handler (non-exponential) before the memoized
    // sub-chord tangent recursion. NOTE: only the bimodal (wrap) case is routed here;
    // the x-monotone case goes through the layers15 path (exposedAreaTangent) — this is the
    // layers15->16 regression fix (test 19). Test 16's x-monotone gaps are handled earlier in
    // solveQueries' reversed-chord branch.
    int d0=1; while(d0<K && h[d0]<3) d0++;
    if(d0<K){
        int TA,TB; bool wR=false,wL=false;
        if(belowArcTangents(d0,A,B,TA,TB,wR,wL) && (wR||wL) && TA!=TB){
            ll r;
            if(straddleExposedArea(A,B,wR,wL,r)) return r;
        }
    }
    bool fbb=false;
    ll r = exposedAreaTangent(1, A, B, fbb);
    return fbb ? convexChainSorted(A, B) : r;
}

// ---- 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]; });
    for(int i=0;i<n;i++) gOrder[i]=order[i];
    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; }
        // upper chain x-increasing = reverse(up)  (= [leftmost, up[U-2], ..., up[1], rightmost])
        upV[K].clear(); upV[K].reserve(up.size());
        for(int t=(int)up.size()-1;t>=0;t--) upV[K].push_back(up[t]);
        upLen[K]=(int)upV[K].size();
        upPref[K].assign(upLen[K]+1, 0);
        for(int i=1;i<upLen[K];i++) upPref[K][i]=upPref[K][i-1]+cross2(upV[K][i-1], upV[K][i]);
        if(upLen[K]>=1) upPref[K][upLen[K]]=upPref[K][upLen[K]-1];
        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; }
        upV[K].clear(); upLen[K]=0; upPref[K].clear();
        K++;
    }
    // x-monotone fast path needs strictly x-increasing chains (no vertical edges).
    xSafe = true;
    for(int d=0; d<K; d++){
        if(h[d] < 3) continue;
        for(int t=1; t<loLen[d]; t++) if(X[vert[d][t]] <= X[vert[d][t-1]]) xSafe=false;
        for(int t=1; t<upLen[d]; t++) if(X[upV[d][t]] <= X[upV[d][t-1]]) xSafe=false;
    }
    gInnerCnt = 0;
    for(int i=0;i<n;i++) if(layer_of[gOrder[i]] >= 1) gInner[gInnerCnt++] = gOrder[i];
}

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]});
        }
        for(int dd=0; dd<K; dd++){ delByLayer[dd].clear(); delLo[dd].clear(); delUp[dd].clear(); }
        for(auto& pr : dels){
            int d = pr.first, p = pr.second;
            delByLayer[d].push_back(p);
            if(h[d] < 3) continue;
            if(p < loLen[d]){
                delLo[d].push_back(p);
                if(p == 0) delUp[d].push_back(0);
                else if(p == loLen[d]-1) delUp[d].push_back(upLen[d]-1);
            } else {
                delUp[d].push_back(h[d] - p);
            }
        }
        for(int dd=0; dd<K; dd++){
            if(delByLayer[dd].size()>1){
                sort(delByLayer[dd].begin(), delByLayer[dd].end());
                delByLayer[dd].erase(unique(delByLayer[dd].begin(), delByLayer[dd].end()), delByLayer[dd].end());
            }
            if(delLo[dd].size()>1){
                sort(delLo[dd].begin(), delLo[dd].end());
                delLo[dd].erase(unique(delLo[dd].begin(), delLo[dd].end()), delLo[dd].end());
            }
            if(delUp[dd].size()>1){
                sort(delUp[dd].begin(), delUp[dd].end());
                delUp[dd].erase(unique(delUp[dd].begin(), delUp[dd].end()), delUp[dd].end());
            }
        }
        int h0=h[0];
        vector<int> del0;
        for(int p : delByLayer[0]) del0.push_back(p);
        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];
                ll newChain;
                bool xdone=false;
                // X-monotone fast path (non-exponential, handles the circle-onion test 16).
                if(X[A] != X[B]){
                    int runLen = (q - p + h0) % h0 + 1;
                    ll xlo = X[A]<X[B] ? X[A] : X[B];
                    ll xhi = X[A]<X[B] ? X[B] : X[A];
                    bool ok = true;
                    for(int st=0; st<runLen; st++){
                        ll xv=X[vert[0][(p+st)%h0]];
                        if(!(xlo < xv && xv < xhi)){ ok=false; break; }
                    }
                    if(ok){ ll r; if(xExposedArea(A,B,r)){ newChain=r; xdone=true; } }
                }
                if(!xdone){
                    // reversed-chord check: a deleted L0 vertex whose t-projection falls outside
                    // [0,|AB|^2] means the chord direction is "reversed"; collectArcs' t-clipping
                    // is not valid there, so route to the tangent path / materialize.
                    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; }
                        }
                    }
                    if(fb){
                        // Reversed-chord/allBelow: tangent-delimited x-monotone/x-bimodal handler
                        // (non-exponential) first, then fall back to the tangent/materialize path.
                        bool straddleDone=false;
                        int d0=1; while(d0<K && h[d0]<3) d0++;
                        if(d0<K){
                            int TA,TB; bool wR=false,wL=false;
                            if(belowArcTangents(d0,A,B,TA,TB,wR,wL) && TA!=TB){
                                ll r;
                                if(wR||wL){
                                    if(straddleExposedArea(A,B,wR,wL,r)){ newChain=r; straddleDone=true; }
                                } else {
                                    if(xmonotoneExposedArea(A,B,d0,TA,TB,r)){ newChain=r; straddleDone=true; }
                                }
                            }
                        }
                        if(!straddleDone){
                            if(innerAllBelow(A,B) && !anyCollinearExtreme(A,B)){
                                bool fbb=false; ll r = exposedAreaTangent(1, A, B, fbb);
                                newChain = fbb ? convexChainSorted(A,B) : r;
                            } else newChain = convexChainSorted(A,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;
}

评测结果