代码

// References:
// [1] saffah_codex_6s_agg2, https://duck.ac/submission/110389:
//     Directly reused our accepted fixed-n NOI2017 clone-hull source with
//     all inherited references below. No separate license notice appeared.
// Approach:
// Dispatch once before the m-query loop on whether n equals 100000.
// The fixed-size copy keeps compile-time constant division; the other
// copy preserves the exact general path. This eliminates an n test per
// generated deletion and permits more constant propagation in the hot loop.
// Purpose:
// Experimental official timing of loop-level fixed-size specialization.
// References:
// [1] duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107361:
//     Directly reused the published NOI2017 clone hull engine, including
//     its inherited citations below. The public source has no separate
//     license notice.
// [2] saffah_codex_6s_agg2, https://duck.ac/submission/107181:
//     Our earlier tangent, hash and hull improvements are inherited in [1]
//     and credited there. No separate license notice appeared.
// Approach:
// In the many official cases whose fixed n equals 100000, compute each
// generated deletion index remainder with a compile-time constant divisor.
// Keep the exact previous path for every other n. The index and output
// remain identical; GCC may reduce the fixed division to a shorter
// reciprocal-multiply sequence.
// Purpose:
// Experimental official timing of constant-divisor index generation.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #107181 <https://duck.ac/submission/107181>
//     （noi17f 榜首 124.293039 ms）。用途：本发的引擎基座 —— 该提交相对本账号 #105479 的三处改动
//     （a 记忆表哈希、b+c 切线谓词"秩条件先行"+vxpad+`lo==pe` 守卫）已由本账号在 #107242 完整落地。
//     本发不改动它们中的任何一处。公开源码未附许可证声明；按本工作区惯例注明账号、地址与内容。
// [2] 本账号（saffah_cc_v41_agg1）在本工作区的提交：#105479（130.282166，基座原件）、
//     #107216（124.860946，a/b/c 移植但缺 a）、#107242（124.195199，a+b+c 完整）、
//     #107244 <https://duck.ac/submission/107244>（123.650178，二级探针按 vy 重编号）、
//     #107263 <https://duck.ac/submission/107263>（123.322，字节偏移寻址）、
//     #107249 <https://duck.ac/submission/107249>（123.501158，**本发的直接基底**：
//     64 位下标 + `(i64)vy.y-(i64)vx.y`）、#107233（124.964212，CH 秩取数试验，已判负）。
// [3] 判题机同款 gcc 9.3 -O2 汇编由本工作区自己取得（godbolt `g93`；`work/nf2_g93run.py`）。
// 上述公开提交均未附许可证声明；按本工作区惯例注明账号、原始提交地址与所用内容。
// ======================
// ===== 思路 =====
// ★ 本发是**单变量**（基底 = #107298）：**把寻址单位从"字节"改成"int"（scale-4 变址）**，
//   使"中点 → 秩取数"的地址**不再需要物化寄存器**：`cmpl (%rcx,%rax,4),%r14d` 直接把变址
//   放进指令里 ⇒ 秩链上"物化基址"的那条 `leaq` 消失（4 条 uop → 3 条）。
//   仍是纯寻址改写（同一批位置、同一批判据），输出逐位不变。
//
// 【判据（判题机 gcc 9.3 -O2 实测；piece 内二级循环"分支前"的链）】
//   基底 #107181 形态 …… leal/sarl/leal/movslq/addq/salq/leaq/cmpl/jl   = 9 条
//   #107244（按 vy 重编号）…… leal/sarl/leal/movslq/salq/leaq/cmpl/jl   = 8 条
//   #107249（64 位下标）…… leaq/sarq/leaq/salq/leaq/cmpl/jl             = 7 条
//   #107263（字节偏移）…… leaq/sarq/andq/leaq/cmpl/jl = 6 条；
//   #107268（vx 用位移）…… leaq/sarq/andq/leaq/cmpl/jl = 6 条，交叉积 4 次取数用位移；
//   #107275（int 单位、scale-4 变址）…… 二级探针到"秩取数"为止 3 条 uop + 取数；
//   **本发：二级探针不变（仍 19 条），但一级（piece 交点）探针 29 条 → 22 条**（判题机 gcc 9.3 实测）：
//     一级的 vy 地址：`movslq QPA+16(,%r9,4),%rcx / addq %rsi,%rcx / cmpl (%rcx),%r14d`
//     一级的 vx 地址：`movslq QPA+4(,%r9,4),%rdx / addq %rsi,%rdx`（原来要 7 条）。
//   ★ 一级探针每个用例执行 **687 万次**（生产等价代理数据实测），是执行次数第二高的循环体。
//     `mid = ((lo+hi)>>1) & ~15`（lo/hi 是 16 的倍数 ⇒ 掩码把"奇数和的 8 字节误差"精确抹掉），
//     随后 `mid` **本身就是** `VC[..]` 的字节偏移 ⇒ 秩取数是一次带基址+变址的 `cmpl`，
//     交叉积的 `vx` 是同一次寻址的 −16 位移 ⇒ 不再需要"下标→偏移→基址"两次换算。
//     ★ 正确性来自 `VC` 的步距恰为 16 B **且 `(lo+hi)` 与 `(lo+hi)-1` 的中点差 8 字节**
//     ⇒ `& ~15` 后与原实现逐位同址（17 份合法输入 + 120 组暴力对拍全部逐位相同）。
//
// 【为什么"链短 1 条"值钱】上一发（#107263，字节偏移，秩链 7→6）实测 **−0.179 ms**；
//   再上一发（#107244，秩链 8→7）实测 **−0.545 ms**：**同一循环里删掉 1 条位于"mid→load"链上的
//   uop（`addq $1`）= −0.545 ms**；而删掉 2 条**不在该链上**的（交叉积侧）只换 −0.149 ms。
//   ⇒ 本循环是**延迟链受限**，不是发射带宽受限 ⇒ 只削"中点→取数→分支"这条链才兑现。
//   （判题机 gcc 的 ins2 全局指令数：1306 → 1254 → 1248，随之单调下降。）
//
// 【正确性】17 份**格式合法**的本地输入（nf2_A~F.in / gtest.in / 2002_t2.in / c45f_in20.txt /
//   n17g_in/g1~g8.in）输出 md5 与 #107249 逐位相同；与 `work/brute.cpp`（逐查询重算凸包）在
//   120 组小数据（5 种点集形态 × 4 档规模 × 6 seed）上全部一致。
//   ⚠ `n17_v1m/t2/noi25/tr/bs/tiny/small/t3` 是旧格式（首行 4 个数、n 可到 1e6 > MAXN），
//   未改动的基线也会 segfault，不是有效对拍集。
// ★ 仪器学：本机（VM）与同题第二席共用 ⇒ 同一份二进制换名后 min-of-13 相交错相差 4.26%，
//   本地任何 <4% 的读数不可判读；本题定价只能走判题机（重复测量 ≈ 40 µs = 0.03%）。
// ================
#pragma GCC target("avx2,bmi2,popcnt,sse4.1,ssse3")
#pragma GCC optimize("O3","rename-registers","web","no-tree-vectorize","no-tree-slp-vectorize")
#include <cstdint>
#include <cstring>

typedef long long i64;
typedef unsigned int u32;
typedef unsigned char u8;
typedef unsigned long long u64;

static const int MAXN = 100005;
static const int MAXL = 104;
static const int MAXDEL = 128;
static const int MAXP = 600;

// fused point record: a = x + 1e8 (u32 wrap), b = y + 1e8, p = ORIGINAL index.
struct PR { u32 a, b, p; };
static PR PRB[2][MAXN];
static int XR[MAXN], YR[MAXN], NYR[MAXN];


#ifdef TRON
#include <cstdio>
#define TRACE(...) fprintf(stderr, __VA_ARGS__)
#else
#define TRACE(...) do {} while (0)
#endif

// ------------------------------------------------------------------ IO
static const u8 *gip; static u8 *gob;
static inline u32 rdu32() {
  while (*gip <= 32) ++gip;
  u32 v = 0;
  while (*gip > 32) { v = v * 10 + (u32)(*gip - '0'); ++gip; }
  return v;
}
static inline i64 rdi64() {
  while (*gip <= 32) ++gip;
  if (*gip == '-') { ++gip; return -(i64)rdu32(); }
  return (i64)rdu32();
}
// parse the next integer; if it fits in u32 (all c_i do) return it via v32, else set the slow flag
static inline u32 rdc(u64 &v32, int &slow) {
  while (*gip <= 32) ++gip;
  if (*gip == '-') { v32 = (u64)rdi64(); slow = 1; return 0; }
  u64 v = 0;
  // lnoi17 SWAR PARSE: the digit loop is 44.2 % of the whole program (perf instructions:u).
  // Eight digits per iteration with ONE bounds test instead of a branch and a dependent imul
  // per digit.  `d` = the raw bytes minus '0'; the range test `((d+6)|d) & 0x80..` is the
  // standard SWAR check that every byte is 0..9.  Byte 0 is the most significant digit, so the
  // pair step pairs (0,1),(2,3),(4,5),(6,7) with no carry between 16-bit lanes (max 99) and the
  // group step combines them as 4-digit halves.  The tail keeps the exact original semantics.
  for (;;) {
    u64 w; __builtin_memcpy(&w, gip, 8);
    u64 d = w - 0x3030303030303030ULL;
    if (((d + 0x0606060606060606ULL) | d) & 0x8080808080808080ULL) break;
    u64 lo = d & 0x000F000F000F000FULL;
    u64 hi = (d >> 8) & 0x000F000F000F000FULL;
    u64 t  = lo * 10u + hi;                                  // 4 x 2-digit, lane 0 is most significant
    u64 a  = t & 0x0000FFFF0000FFFFULL;                      // p0 , p2
    u64 b  = (t >> 16) & 0x0000FFFF0000FFFFULL;              // p1 , p3
    u64 s  = a * 100u + b;                                   // (p0 p1) , (p2 p3)
    v = v * 100000000ULL + (s & 0xFFFFFFFFULL) * 10000ULL + (s >> 32);
    gip += 8;
  }
  while (*gip > 32) { v = v * 10 + (u32)(*gip - '0'); ++gip; }
  if (v > 0x7fffffffuLL) { v32 = v; slow = 1; return 0; }
  slow = 0; v32 = v;
  return (u32)v;
}
static const char HEXD[201] =
    "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
    "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";
static inline void wr(i64 v) {
  // 17 digits is the common line on the max test.  Two exact-length changes (no byte is ever
  // written outside [gob, gob+len)): digits come out four at a time, halving the 64-bit
  // divides -- the only expensive op in the loop -- and the variable-length memcpy, which gcc
  // turns into a call, becomes fixed 8-byte moves.  The len<8 path keeps a byte loop: the
  // earlier version tested `len <= 16` without first requiring len >= 8, so a one-digit answer
  // wrote 7 bytes BELOW gob (Runtime Error on testcase 1, the only case it broke).
  u8 buf[40]; u8 *o = buf + 32;
  u64 x = (u64)v;
  while (x >= 10000) { u32 r = (u32)(x % 10000); x /= 10000;
    u32 r2 = r % 100; r /= 100;
    o -= 4; memcpy(o, HEXD + r * 2, 2); memcpy(o + 2, HEXD + r2 * 2, 2); }
  while (x >= 100) { u32 r = (u32)(x % 100); x /= 100; o -= 2; memcpy(o, HEXD + r * 2, 2); }
  if (x >= 10) { o -= 2; memcpy(o, HEXD + x * 2, 2); } else *--o = (u8)('0' + (u32)x);
  u32 len = (u32)(buf + 32 - o);
  if (len >= 8) {
    memcpy(gob, o, 8);
    if (len <= 16) memcpy(gob + len - 8, o + len - 8, 8);
    else { memcpy(gob + 8, o + 8, 8); memcpy(gob + len - 8, o + len - 8, 8); }
  } else {
    for (u32 i2 = 0; i2 < len; i2++) gob[i2] = o[i2];
  }
  gob += len; *gob++ = '\n';
}

// ------------------------------------------------------------------ layer storage
struct VX { int rk, x, y, vxpad; };
static VX   VC1[MAXN + 8], VC2[MAXN + 8];
static int  CHP1[MAXN + 8], CHP2[MAXN + 8];
static i64  PF1[MAXN + MAXL + 8], PF2[MAXN + MAXL + 8];
static u32  CP1[MAXN], CP2[MAXN];

struct LYS {
  int *X, *Y;
  VX *VC;         // compact vertices (rank, x, y) in chain order
  int *CH;        // concatenated chains (ranks)
  i64 *PF;        // per-layer prefix sums of consecutive cross terms
  int LOF[MAXL], LSZ[MAXL];
  i64 PFOF[MAXL];
  u32 *CP;        // per hulled rank: (local chain position << 8) | (layer, 1-based)
  int N, NL, TAG;
  // ---- lazy peel state (layers are produced one at a time, on demand) ----
  int *alive, *alive2;
  int na;         // # alive points not yet placed in a layer
  int cw;         // next free chain slot
  int pd;         // next layer to peel (1-based)
  int done;       // no layer can be peeled any more
};

static int ALV1[MAXN], ALV2_[MAXN], ALV3[MAXN], ALV4[MAXN];
static int ST[MAXN], STX[MAXN], STY[MAXN];

static void peel_init(LYS &H, int *start, int nstart) {
  int n = H.N;
  for (int i = 1; i <= n; i++) H.CP[i] = 0;
  H.na = nstart;
  int *alive = H.alive;
  for (int i = 1; i <= nstart; i++) alive[i] = start[i];
  H.cw = 0; H.NL = 0; H.pd = 1; H.done = 0;
}

// peel exactly one more layer (H.pd), advancing the saved state
static u8 L1F[MAXN + 1];
static i64 A1C, A2C;
// n17y: bit0 = rank is on h1's layer 1 (the upper hull), bit1 = on h2's layer 1.
// Deleting only points off a hull's layer 1 leaves that hull (and its half of the
// shoelace sum) untouched, so the half is the constant A1C / A2C.
static void peel_one(LYS &H) {
  if (H.done) return;
  int d = H.pd;
  if (d > 101) { H.done = 1; return; }
  int n = H.N, na = H.na;
  if (!na) { H.done = 1; return; }
  int *alive = H.alive, *alive2 = H.alive2;
  int tp = 0;
  const int *PXa = H.X; const int *PYa = H.Y;
  for (int ti = 1; ti <= na; ti++) {
    int i = alive[ti];
    int xi = PXa[i], yi = PYa[i];
    while (tp > 1) {
      int p = ST[tp - 1], q = ST[tp];
      i64 c = (i64)(STX[tp] - STX[tp - 1]) * (yi - STY[tp - 1]) - (i64)(STY[tp] - STY[tp - 1]) * (xi - STX[tp - 1]);
      if (c > 0) tp--; else break;
    }
    ST[++tp] = i; STX[tp] = xi; STY[tp] = yi;
  }
  if (!tp) { H.done = 1; return; }
  H.NL = d;
  H.LOF[d] = H.cw;
  H.LSZ[d] = tp;
  for (int i = 1; i <= tp; i++) { int r = ST[i]; H.CH[H.cw] = r; H.VC[H.cw].rk = r; H.VC[H.cw].x = H.X[r]; H.VC[H.cw].y = H.Y[r]; H.CP[r] = ((u32)(H.cw - H.LOF[d]) << 8) | (u32)d; H.cw++; }
  for (int i = H.LOF[d]; i + 1 < H.cw; ++i) H.VC[i].vxpad = H.VC[i + 1].x - H.VC[i].x;
  if (d == 1) { u8 tg = (u8)H.TAG; for (int i = 1; i <= tp; i++) L1F[ST[i]] |= tg; }
  if (d == 1) H.PFOF[1] = 0; else H.PFOF[d] = H.PFOF[d - 1] + H.LSZ[d - 1] + 1;
  i64 *pf = H.PF + H.PFOF[d];
  pf[0] = 0;
  for (int i = 0; i < tp; i++) {
    i64 add = 0;
    if (i + 1 < tp) {
      int a = H.CH[H.LOF[d] + i], b = H.CH[H.LOF[d] + i + 1];
      add = (i64)H.X[a] * H.Y[b] - (i64)H.Y[a] * H.X[b];
    }
    pf[i + 1] = pf[i] + add;
  }
  int nb = 0;
  for (int ti = 1; ti <= na; ti++) { int i = alive[ti]; if ((H.CP[i] & 255u) != (u32)d) alive2[++nb] = i; }
  { int *tmp = alive; alive = alive2; alive2 = tmp; H.alive = alive; H.alive2 = alive2; }
  H.na = nb;
  H.pd = d + 1;
  if (!nb) H.done = 1;
}

// make sure layers 1..d have been produced (or the peel is exhausted)
static void peel_to(LYS &H, int d) {
  while (!H.done && H.pd <= d) peel_one(H);
}

static int UNR[MAXDEL + 4];

// Depth of the first deletion-free layer, peeling layers on demand.
// The shallow layers are tested with a flat scan over the deleted ranks (they resolve in
// one step, so the scan breaks early); past SHALLOW the ranks are resolved one at a time
// instead, which keeps a deep run O(#deleted) rather than O(depth * #deleted).
// lnoi17 SCAN FUSION: hull2's bucketing loop re-reads exactly the same `H.CP[del[z]] & 255u`
// values that peel_depth's depth scan just read -- measured on the board's own inputs, the two
// scans have IDENTICAL element counts (4 799 214 and 3 082 284) and peel_depth calls it 200 000
// times, always down the fast path.  So the first scan now also does the bucketing and the second
// one is deleted: HALF of this row's ~4.8 M random u32 loads into the 400 KB CP array.
static int peel_depth(LYS &H, const int *del, int nd, int *wcnt, int (*wrk)[MAXDEL + 4]) {
  int D;
  peel_to(H, 8);
  {
    const u32 *cp = H.CP;
    unsigned m = 0;
    for (int z = 0; z < nd; z++) { int x = del[z]; unsigned c = cp[x] & 255u; if (c - 1u < 8u) m |= 1u << c; wrk[c][wcnt[c]++] = (int)(cp[x] >> 8); }
    if (m != 0x1FEu) {                   // some layer in 1..8 holds no deletion
      int j = __builtin_ctz((~m) & 0x1FEu);
      return (j <= H.NL) ? j : H.NL + 1;
    }
  }
  D = 9;
  int left = nd;
  for (int z = 0; z < nd; z++) UNR[z] = del[z];
  (void)0;
  for (;; D++) {
    peel_to(H, D);
    if (D > H.NL) return D;
    const u32 *cp = H.CP;
    int hit = 0;
    for (int z = 0; z < left; ) {
      if ((cp[UNR[z]] & 255u) == (u32)D) { hit = 1; UNR[z] = UNR[--left]; } else z++;
    }
    if (!hit) return D;
    if (D >= 101) return 102;            // every layer is hit: hull is not representable
  }
}

// ------------------------------------------------------------------ query state
// A piece is a contiguous run of one layer chain, kept as its index interval.
//   cb  : index into H.VC/H.CH of the piece's first vertex
//   len : number of vertices
//   pf0 : index into H.PF of the piece's first prefix entry  (PFOF[d]+lo)
//   pf1 : index into H.PF of the piece's last  prefix entry  (PFOF[d]+hi)
struct PC { int cbb, cbe, pf0, pf1; };   // n17y: BYTE offsets into H.VC (16 x vertex index)
static PC QPA[MAXP];
static int QNP;

// qlocate() used to live here: two binary searches per ins2 call just to recover a piece
// index that qryl2/qryr2 already knew.  Both now return it, so it is gone.

// tangent search for the left cut: returns the global position A of the tangent vertex,
// or -1 when the whole chain is dropped.
static int qryl2(const LYS &H, int k, i64 kx, i64 ky, int &outpi) {
  outpi = -1;
  if (QNP == 0) return -1;
  const VX *VC = H.VC;
  const char *VCB = (const char *)VC;
  const int *QP = (const int *)QPA;
  if (*(const int *)(VCB + QPA[0].cbb) > k) return -1;
  int found = -1;
  { // binary search over piece-boundary junctions
    int lo = 0, hi = QNP - 2;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      const VX &vx = *(const VX *)(VCB + QP[4 * mid + 1]);
      const VX &vy = *(const VX *)(VCB + QP[4 * mid + 4]);
      if (vy.rk > k || ((i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx)) > 0) { found = mid; hi = mid - 1; } else lo = mid + 1;
    }
  }
  int pi = (found >= 0) ? found : QNP - 1;
  outpi = pi;
  const PC &pp = QPA[pi];
  int pe = (pp.cbe - pp.cbb) >> 4;
  int jhi = (found >= 0) ? pe : pe - 1;
  if (jhi < 0) return pe;
  const int *VB = (const int *)(VCB + pp.cbb);
  i64 lo = 4, hi = 4 * (i64)(jhi + 1);
  while (lo < hi) {
    i64 mid = (((lo + hi) >> 1) & ~(i64)3);
    if (VB[mid] > k || ((i64)(VB[mid - 3] - kx) * ((i64)VB[mid + 2] - (i64)VB[mid - 2]) - (i64)(VB[mid - 2] - ky) * VB[mid - 1]) > 0) hi = mid; else lo = mid + 4;
  }
  {
    if (lo == 4 * (i64)(pe + 1)) return pe;
    i64 mid = lo;
    if (!(VB[mid] > k || ((i64)(VB[mid - 3] - kx) * ((i64)VB[mid + 2] - (i64)VB[mid - 2]) - (i64)(VB[mid - 2] - ky) * VB[mid - 1]) > 0)) return pe;
  }
  return (lo >> 2) - 1;
}

// tangent search for the right cut: returns the global position B of the first kept vertex
// of the right part, or V when the right part is empty.
static int qryr2h(const LYS &H, int k, i64 kx, i64 ky, int &outpi, int astart) {
  outpi = -1;
  if (QNP == 0) return -1;
  const VX *VC = H.VC;
  const char *VCB = (const char *)VC;
  const int *QP = (const int *)QPA;
  const PC &pl = QPA[QNP - 1];
  if (*(const int *)(VCB + pl.cbe) < k) return -1;
  int found = -1;
  {
    int lo = astart, hi = QNP - 2;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      const VX &vx = *(const VX *)(VCB + QP[4 * mid + 1]);
      const VX &vy = *(const VX *)(VCB + QP[4 * mid + 4]);
      if (vx.rk >= k && ((i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx)) <= 0) { found = mid; hi = mid - 1; } else lo = mid + 1;
    }
  }
  int pi = (found >= 0) ? found : QNP - 1;
  outpi = pi;
  const PC &pp = QPA[pi];
  int pe = (pp.cbe - pp.cbb) >> 4;
  int jhi = (found >= 0) ? pe : pe - 1;
  if (jhi < 0) return pe;
  const int *VB = (const int *)(VCB + pp.cbb);
  i64 lo = 4, hi = 4 * (i64)(jhi + 1);
  while (lo < hi) {
    i64 mid = (((lo + hi) >> 1) & ~(i64)3);
    if (VB[mid - 4] >= k && ((i64)(VB[mid - 3] - kx) * ((i64)VB[mid + 2] - (i64)VB[mid - 2]) - (i64)(VB[mid - 2] - ky) * VB[mid - 1]) <= 0) hi = mid; else lo = mid + 4;
  }
  {
    if (lo == 4 * (i64)(pe + 1)) return pe;
    i64 mid = lo;
    if (!(VB[mid - 4] >= k && ((i64)(VB[mid - 3] - kx) * ((i64)VB[mid + 2] - (i64)VB[mid - 2]) - (i64)(VB[mid - 2] - ky) * VB[mid - 1]) <= 0)) return pe;
  }
  return (lo >> 2) - 1;
}

static void ins2(const LYS &H, int d, int lo, int hi) {
  if (lo > hi) return;
  int cb = H.LOF[d] + lo, ln = hi - lo + 1;
  int cbb = cb << 4, cbe = (cb + ln - 1) << 4;
  int pfa = H.PFOF[d] + lo, pfb = H.PFOF[d] + hi;
  if (QNP == 0) { QNP = 1; QPA[0].cbb = cbb; QPA[0].cbe = cbe; QPA[0].pf0 = pfa; QPA[0].pf1 = pfb; return; }
  const VX *VC = H.VC;
  const VX &vL = VC[cb], &vR = VC[cb + ln - 1];
  int Ap = -1, Bp = -1;
  int A = qryl2(H, vL.rk, vL.x, vL.y, Ap);
  int B = qryr2h(H, vR.rk, vR.x, vR.y, Bp, Ap > 0 ? Ap : 0);
  // IN-PLACE splice.  Layout: the prefix [0..ia-1] does not move; the truncated piece
  // stays at index ia; the new piece goes to ia+1; the trimmed trailing piece to ia+2;
  // the tail to ia+3... (with ia = -1 meaning "no prefix", shifting everything down).
  // ORDERING MATTERS: the tail is moved into its final place FIRST, and both source
  // pieces are read out first, because the new/trim pieces land on indices the tail
  // still has to read.  The tail move runs backward when its destination is ahead of
  // its source and forward otherwise -- each is the only safe direction for its shift.
  int ia = -1, offa = 0, ib = -1, offb = 0;
  if (A >= 0) { ia = Ap; offa = A; }   // the search returns the piece-local offset
  if (B >= 0) { ib = Bp; offb = B; }
  PC pia, pib;
  if (ia >= 0) pia = QPA[ia];
  if (ib >= 0) pib = QPA[ib];
  int hd = (ia >= 0) ? ia + 1 : 0;      // index of the new piece
  int nt = (ib >= 0) ? QNP - ib - 1 : 0;
  int dst = hd + ((ib >= 0) ? 2 : 1);   // first tail destination
  if (nt > 0) {
    if (dst > ib + 1) { for (int q = QNP - 1, d = dst + nt - 1; q > ib; q--, d--) QPA[d] = QPA[q]; }
    else { for (int q = ib + 1, d = dst; q < QNP; q++, d++) QPA[d] = QPA[q]; }
  }
  if (ia >= 0) { QPA[ia].cbe = pia.cbb + (offa << 4); QPA[ia].pf1 = pia.pf0 + offa; }
  QPA[hd].cbb = cbb; QPA[hd].cbe = cbe; QPA[hd].pf0 = pfa; QPA[hd].pf1 = pfb;
  if (ib >= 0) {
    QPA[hd + 1].cbb = pib.cbb + (offb << 4); QPA[hd + 1].cbe = pib.cbe;
    QPA[hd + 1].pf0 = pib.pf0 + offb; QPA[hd + 1].pf1 = pib.pf1;
  }
  QNP = hd + ((ib >= 0) ? 2 : 1) + nt;
}

static i64 hull2(LYS &H, const int *c, int k, int *wcnt, int (*wrk)[MAXDEL + 4]) {
  int i = peel_depth(H, c, k, wcnt, wrk) - 1;
  if (i + 1 <= H.NL) {
    int d0 = i + 1;
    QNP = 1;
    QPA[0].cbb = H.LOF[d0] << 4; QPA[0].cbe = (H.LOF[d0] + H.LSZ[d0] - 1) << 4;
    QPA[0].pf0 = H.PFOF[d0]; QPA[0].pf1 = H.PFOF[d0] + H.LSZ[d0] - 1;
  }
  else QNP = 0;
  while (i) {
    int d = wcnt[i];
    if (d) {
      int *W = wrk[i];
      for (int a = 1; a < d; a++) { int v = W[a], b = a - 1; while (b >= 0 && W[b] > v) { W[b + 1] = W[b]; b--; } W[b + 1] = v; }
      int sz = H.LSZ[i];
      int cur = 0;                       // first chain position not yet consumed
      for (int a = 0; a < d; a++) {
        int L = W[a];
        if (cur < L) ins2(H, i, cur, L - 1);     // surviving run before the deleted key
        cur = L + 1;                             // skip the deleted vertex itself
      }
      if (cur < sz) ins2(H, i, cur, sz - 1);
    }
    i--;
  }
  // RESET WITHOUT RE-READING CP.  Every bucket the scan above can touch is indexed by
  // `cp[x] & 255`, which is either 0 or a layer in 1..H.NL, so the buckets that can be
  // dirty are exactly 0..H.NL -- known without a single CP load.  The old form re-read
  // `H.CP[c[z]]` (a 400 KB array, 7.7 random loads per call, 1.54 M in the run) purely to
  // recover an index that the reset can enumerate.
  { int hi = H.NL; if (hi > 101) hi = 101; for (int c2 = 0; c2 <= hi; c2++) wcnt[c2] = 0; }
  i64 tot = 0;
  for (int q = 0; q < QNP; q++) tot += H.PF[QPA[q].pf1] - H.PF[QPA[q].pf0];
  { const char *VCB = (const char *)H.VC;
    for (int q = 0; q + 1 < QNP; q++) {
      const PC &p0 = QPA[q], &p1 = QPA[q + 1];
      const VX &a = *(const VX *)(VCB + p0.cbe);
      const VX &b = *(const VX *)(VCB + p1.cbb);
      tot += (i64)a.x * b.y - (i64)a.y * b.x;
    }
    if (QNP > 0) {
      const PC &p0 = QPA[QNP - 1], &p1 = QPA[0];
      const VX &a = *(const VX *)(VCB + p0.cbe);
      const VX &b = *(const VX *)(VCB + p1.cbb);
      tot += (i64)a.x * b.y - (i64)a.y * b.x;
    }
  }
  return -tot;
}

// ------------------------------------------------------------------ solve
static int WCNT[MAXL + 2];
static int WRK[MAXL + 2][MAXDEL + 4];
// packed dedup table: (rank << 15) | stamp.  rank <= n <= 100004 < 2^17, stamp in [1, 32767].
static u32 RKT[MAXN + 1];
static u32 CURSTAMP;
static int DELR[MAXDEL], DELG[MAXDEL];

static LYS h1, h2;

// ------------------------------------------------------------------ answer memo
// The per-query answer S = a1 + a2 depends ONLY on the multiset of deleted ranks:
// hull2's result is the hull area of the remaining points, and the lazy peel state is
// a pure cache.  The deleted ranks are drawn from a small universe on this data, so the
// same SET recurs; a hit skips both hull2 calls (the whole cost of the query).
// The key must be ORDER-INDEPENDENT: DELR is in first-occurrence order, which differs
// between two queries that delete the same set along different sample paths.
static const int MWS = 1 << 14;   // n17f: 4-way x 2^14 sets = 1 MB (was 2^15 = 2 MB)
struct MS4 { u64 k0, k1, k2, k3; i64 v0, v1, v2, v3; };
static MS4 MT[MWS];
static inline u64 ahash(const int *d, int nd) {
  u64 sa = 0x243F6A8885A308D3ULL + (u64)nd, sb = 0x13198A2E03707344ULL;
  for (int z = 0; z < nd; z++) {
    u64 x = (u32)d[z];
    x *= 0x2545F4914F6CDD1DULL;
    sa += x; sb ^= x;
  }
  u64 h = (sa * 0x9E3779B97F4A7C15ULL) ^ (sb * 0xC2B2AE3D27D4EB4FULL);
  h ^= h >> 31; if (!h) h = 1;
  return h;
}

static void solve() {
  int n = (int)rdu32();
  // `cv % (u32)n` is a 32-bit DIVISION (~26 cyc) on the per-deletion critical path.
  // NM = ceil(2^32/n) turns it into one imul + one shift + one imul + one cmov: q is
  // either floor(cv/n) or one too big, and the conditional add repairs that.  The
  // identity was validated against `%` on 34,011,626 (a,n) pairs with 0 mismatches.
  const u64 NM = (0xFFFFFFFFULL / (u64)(u32)n) + 1;
  int m = (int)rdu32();
  PR *rsrc = PRB[0], *rdst_ = PRB[1];
  for (int i = 0; i < n; i++) {
    u32 aa = (u32)((int)rdi64() + 100000000);
    u32 bb = (u32)((int)rdi64() + 100000000);
    rsrc[i].a = aa; rsrc[i].b = bb; rsrc[i].p = (u32)i;
  }
  {
    static int cnt[1 << 16];
    for (int half = 0; half < 2; half++) {          // half 0 -> field b (low key), half 1 -> field a
      for (int lo = 0; lo < 2; lo++) {
        int shift = lo * 16;
        memset(cnt, 0, sizeof(cnt));
        if (half == 0) {
          for (int i = 0; i < n; i++) cnt[(int)((rsrc[i].b >> shift) & 0xFFFFu)]++;
          int sum = 0;
          for (int i = 0; i < (1 << 16); i++) { int c = cnt[i]; cnt[i] = sum; sum += c; }
          for (int i = 0; i < n; i++) { PR r = rsrc[i]; rdst_[cnt[(int)((r.b >> shift) & 0xFFFFu)]++] = r; }
        } else {
          for (int i = 0; i < n; i++) cnt[(int)((rsrc[i].a >> shift) & 0xFFFFu)]++;
          int sum = 0;
          for (int i = 0; i < (1 << 16); i++) { int c = cnt[i]; cnt[i] = sum; sum += c; }
          for (int i = 0; i < n; i++) { PR r = rsrc[i]; rdst_[cnt[(int)((r.a >> shift) & 0xFFFFu)]++] = r; }
        }
        PR *t = rsrc; rsrc = rdst_; rdst_ = t;
      }
    }
  }
  for (int r = 1; r <= n; r++) {
    const PR &q = rsrc[r - 1];
    int xx = (int)q.a - 100000000, yy = (int)q.b - 100000000;
    XR[r] = xx; YR[r] = yy; NYR[r] = -yy; RKT[q.p + 1] = (u32)r << 15;
  }
  static int GREP[MAXN], GCNT[MAXN], GCUR[MAXN], REPL[MAXN];
  RKT[0] = 0u;   // index 0 is never probed (idx+1 >= 1); its stamp is 0, never equal to CURSTAMP
  int nrep = 0;
  for (int r = 1; r <= n; r++) {
    if (r > 1 && XR[r] == XR[r - 1] && YR[r] == YR[r - 1]) { GREP[r] = GREP[r - 1]; GCNT[GREP[r]]++; }
    else { GREP[r] = r; GCNT[r] = 1; REPL[++nrep] = r; }
  }
  h1.N = n; h1.X = XR; h1.Y = YR; h1.CH = CHP1; h1.VC = VC1; h1.PF = PF1; h1.CP = CP1; h1.TAG = 1;
  h2.N = n; h2.X = XR; h2.Y = NYR; h2.CH = CHP2; h2.VC = VC2; h2.PF = PF2; h2.CP = CP2; h2.TAG = 2;
  h1.alive = ALV1; h1.alive2 = ALV2_; h2.alive = ALV3; h2.alive2 = ALV4;
  peel_init(h1, REPL, nrep);
  peel_init(h2, REPL, nrep);
  peel_to(h1, 8); peel_to(h2, 8);      // layer 1 of both hulls is now known
  A1C = hull2(h1, DELR, 0, WCNT, WRK); // k = 0  =>  the untouched layer-1 shoelace
  A2C = hull2(h2, DELR, 0, WCNT, WRK);
  i64 S = -1;
  u32 Smod = (u32)(n - 1);          // S mod n, with S = -1 initially
  // DIVISION-FREE S mod n: `S % (i64)n` is a 64-bit idiv and S feeds the NEXT query's
  // sample indices, so it sits inside the 1e5-long dependent chain.
  const u32 un = (u32)n;
  const u64 invn = (un <= 1u) ? 0ULL : (u64)(((unsigned __int128)1 << 64) / un);
  const int NODUP = (nrep == n);
  if (n == 100000) {
  for (int step = 0; step < m; step++) {
    int k = (int)rdu32();
    if (++CURSTAMP >= 32768u) {                 // stamp wrapped: clear all stamps SEQUENTIALLY
      for (int i = 0; i <= (int)n; i++) RKT[i] &= 0xFFFF8000u;   // ranks (high 17 bits) survive
      CURSTAMP = 1u;
    }
    int nd = 0, ndg = 0; u32 mask = 0;
    if (NODUP) {
      for (int i = 0; i < k; i++) {
        u64 bigv; int slow;
        u32 cv = rdc(bigv, slow);
        int idx;
        if (slow) {
          i64 v = ((i64)S + (i64)bigv) % n;
          if (v < 0) v += n;
          idx = (int)v;
        } else {
            u32 t = Smod + cv % 100000u;
            if (t >= 100000u) t -= 100000u;
            idx = (int)t;

        }
        u32 e = RKT[idx + 1];
        if ((e & 32767u) != CURSTAMP) { RKT[idx + 1] = (e & 0xFFFF8000u) | CURSTAMP; int rk = (int)(e >> 15); DELR[nd++] = rk; mask |= L1F[rk]; }
      }
      // GCUR[DELR[i]] = 0 used to run here.  GCUR is read ONLY in the !NODUP branch
      // below (`++GCUR[g]`), and NODUP is loop-invariant, so on an input with no
      // duplicate point these nd random stores per query are dead: nd ~ 15 x 1e5
      // queries = 1.49 M random cache-line RFOs into a 400 KB array, written, never read.
    } else {
    for (int i = 0; i < k; i++) {
      u64 bigv; int slow;
      u32 cv = rdc(bigv, slow);
      int idx;
      if (slow) {
        i64 v = ((i64)S + (i64)bigv) % n;
        if (v < 0) v += n;
        idx = (int)v;
      } else {
          u32 t = Smod + cv % 100000u;
          if (t >= 100000u) t -= 100000u;
          idx = (int)t;

      }
      u32 e = RKT[idx + 1];
      int rk = (int)(e >> 15);
      if ((e & 32767u) != CURSTAMP) {
        RKT[idx + 1] = (e & 0xFFFF8000u) | CURSTAMP;
        int g = GREP[rk];
        if (++GCUR[g] == GCNT[g]) { DELR[nd++] = g; mask |= L1F[g]; }
        DELG[ndg++] = g;
      }
    }
    for (int i = 0; i < ndg; i++) GCUR[DELG[i]] = 0;
    }
    u64 mh = ahash(DELR, nd);
    MS4 &e = MT[mh & (u64)(MWS - 1)];
    if (e.k0 == mh) { S = e.v0; }
    else if (e.k1 == mh) { S = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else if (e.k2 == mh) { S = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else if (e.k3 == mh) { S = e.v3; e.k3 = e.k2; e.v3 = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else {
      i64 a1 = (mask & 1u) ? hull2(h1, DELR, nd, WCNT, WRK) : A1C;
      i64 a2 = (mask & 2u) ? hull2(h2, DELR, nd, WCNT, WRK) : A2C;
      S = a1 + a2;
      e.k3 = e.k2; e.v3 = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S;
    }
    if (un <= 1u) { Smod = 0u; }
    else {
      u64 qq = (u64)(((unsigned __int128)(u64)S * invn) >> 64);
      u64 rr2 = (u64)S - qq * (u64)un;
      if (rr2 >= (u64)un) rr2 -= (u64)un;
      Smod = (u32)rr2;
    }
    wr(S);
  }
  } else {
  for (int step = 0; step < m; step++) {
    int k = (int)rdu32();
    if (++CURSTAMP >= 32768u) {                 // stamp wrapped: clear all stamps SEQUENTIALLY
      for (int i = 0; i <= (int)n; i++) RKT[i] &= 0xFFFF8000u;   // ranks (high 17 bits) survive
      CURSTAMP = 1u;
    }
    int nd = 0, ndg = 0; u32 mask = 0;
    if (NODUP) {
      for (int i = 0; i < k; i++) {
        u64 bigv; int slow;
        u32 cv = rdc(bigv, slow);
        int idx;
        if (slow) {
          i64 v = ((i64)S + (i64)bigv) % n;
          if (v < 0) v += n;
          idx = (int)v;
        } else {
            u32 qq = (u32)((NM * (u64)cv) >> 32);
            i64 rr = (i64)cv - (i64)qq * (i64)(u32)n;
            if (rr < 0) rr += (i64)(u32)n;
            u32 t = Smod + (u32)rr;
            if (t >= (u32)n) t -= (u32)n;
            idx = (int)t;

        }
        u32 e = RKT[idx + 1];
        if ((e & 32767u) != CURSTAMP) { RKT[idx + 1] = (e & 0xFFFF8000u) | CURSTAMP; int rk = (int)(e >> 15); DELR[nd++] = rk; mask |= L1F[rk]; }
      }
      // GCUR[DELR[i]] = 0 used to run here.  GCUR is read ONLY in the !NODUP branch
      // below (`++GCUR[g]`), and NODUP is loop-invariant, so on an input with no
      // duplicate point these nd random stores per query are dead: nd ~ 15 x 1e5
      // queries = 1.49 M random cache-line RFOs into a 400 KB array, written, never read.
    } else {
    for (int i = 0; i < k; i++) {
      u64 bigv; int slow;
      u32 cv = rdc(bigv, slow);
      int idx;
      if (slow) {
        i64 v = ((i64)S + (i64)bigv) % n;
        if (v < 0) v += n;
        idx = (int)v;
      } else {
          u32 qq = (u32)((NM * (u64)cv) >> 32);
          i64 rr = (i64)cv - (i64)qq * (i64)(u32)n;
          if (rr < 0) rr += (i64)(u32)n;
          u32 t = Smod + (u32)rr;
          if (t >= (u32)n) t -= (u32)n;
          idx = (int)t;

      }
      u32 e = RKT[idx + 1];
      int rk = (int)(e >> 15);
      if ((e & 32767u) != CURSTAMP) {
        RKT[idx + 1] = (e & 0xFFFF8000u) | CURSTAMP;
        int g = GREP[rk];
        if (++GCUR[g] == GCNT[g]) { DELR[nd++] = g; mask |= L1F[g]; }
        DELG[ndg++] = g;
      }
    }
    for (int i = 0; i < ndg; i++) GCUR[DELG[i]] = 0;
    }
    u64 mh = ahash(DELR, nd);
    MS4 &e = MT[mh & (u64)(MWS - 1)];
    if (e.k0 == mh) { S = e.v0; }
    else if (e.k1 == mh) { S = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else if (e.k2 == mh) { S = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else if (e.k3 == mh) { S = e.v3; e.k3 = e.k2; e.v3 = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S; }
    else {
      i64 a1 = (mask & 1u) ? hull2(h1, DELR, nd, WCNT, WRK) : A1C;
      i64 a2 = (mask & 2u) ? hull2(h2, DELR, nd, WCNT, WRK) : A2C;
      S = a1 + a2;
      e.k3 = e.k2; e.v3 = e.v2; e.k2 = e.k1; e.v2 = e.v1; e.k1 = e.k0; e.v1 = e.v0; e.k0 = mh; e.v0 = S;
    }
    if (un <= 1u) { Smod = 0u; }
    else {
      u64 qq = (u64)(((unsigned __int128)(u64)S * invn) >> 64);
      u64 rr2 = (u64)S - qq * (u64)un;
      if (rr2 >= (u64)un) rr2 -= (u64)un;
      Smod = (u32)rr2;
    }
    wr(S);
  }
  }
}
// ------------------------------------------------------------------ main
static u8 inbuf[128 << 20];
static u8 outbuf[32 << 20];
#ifdef LOCAL_MAIN
#include <cstdio>
int main(int argc, char **argv) {
  FILE *f = argc > 1 ? fopen(argv[1], "rb") : stdin;
  if (!f) { fprintf(stderr, "no file\n"); return 1; }
  size_t n = fread(inbuf, 1, sizeof(inbuf), f);
  if (argc > 1) fclose(f);
  gip = inbuf;
  gob = outbuf;
  solve();
  fwrite(outbuf, 1, gob - outbuf, stdout);
  return 0;
}
#else
#if !defined(HARNESS)
int main() { return 0; }   // stub referenced by crt1.o (never called)
struct DI {
  unsigned long abi_version; const char *stdin_ptr; unsigned long stdin_size;
  char *stdout_ptr; unsigned long stdout_limit; unsigned long stdout_size;
  char *stderr_ptr; unsigned long stderr_limit; unsigned long stderr_size;
  const char *IB_ptr; unsigned long IB_limit;
  char *OB_ptr; unsigned long OB_limit;
  unsigned long tsc_frequency;
} __attribute__((packed));
extern "C" void __libc_start_main(void *m, long argc, char **argv) {
  (void)m;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++; p++;
  DI *d = 0;
  for (; p[0]; p += 2) if (p[0] == 0x6b637564UL) { d = (DI *)p[1]; break; }
  if (d) {
    gip = (const u8 *)d->stdin_ptr;
    gob = (u8 *)d->stdout_ptr;
    solve();
    d->stdout_size = (unsigned long)(gob - (u8 *)d->stdout_ptr);
  }
  __asm__ volatile("syscall"::"a"(60), "D"(0):"rcx", "r11", "memory");
  for (;;) {}
}
#endif
#endif

评测结果