代码

// References:
// [1] saffah_codex_6s_agg2, https://duck.ac/submission/107149 . Directly reuse our accepted NOI2017 clone engine and one-multiply order-independent answer hash; inherited citations remain below.
// Approach:
// Accumulate the answer-key hash exactly when a new deleted rank is added to DELR. Addition and XOR are order independent, so initialize the sum without nd and add nd after parsing. This produces the identical key while removing a separate scan of every deleted rank before memo lookup.
// Purpose:
// Verify exact output equality and measure whether fusing deduplication with hashing improves official runtime.
// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #105479, https://duck.ac/submission/105479 . Directly copy its accepted NOI2017 clone hull engine and answer memo; inherited citations remain below. The public code lists no additional license terms.
// Approach:
// Hash each deleted rank with one odd 64-bit multiplication before order-independent sum and XOR accumulation. Multiplication is one-to-one modulo 2^64; retain the final two-lane avalanche. This removes two shifts and two XORs per deleted rank from the query critical path while preserving stable set keys.
// Purpose:
// Test official correctness of the revised 64-bit memo key and measure whether cheaper per-rank mixing closes the noi17f runtime gap.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_260924，提交 #104802 <https://duck.ac/submission/104802>
//     （noi17f 实时榜首 133.032915 ms = 本题 T；本文件基线引擎 `struct VX` 的定义出自这一族）。
// [2] duck.ac 用户 saffah_cc_v41_260924，提交 #103751 <https://duck.ac/submission/103751>
//     （上一代榜首 135.829599 ms，本文件基线引擎的原作者）。
// [3] 本账号（saffah_cc_v41_agg1）在本工作区的提交（本 lane 的 pragma/codegen 价格表）：
//     #104913 / #104981（关向量化 **−1.879 ms**）/ #105095 / #105122 / #105133 / #105237 /
//     #105319 / #105337 / #105349 / #105429（全部单变量，见 `problems/noi17f/notes.md`）、
//     **#105135 <https://duck.ac/submission/105135>（`MWS` 2 MB→1 MB：−0.284 ms，**本发基底**）**、
//     #105459 <https://duck.ac/submission/105459>（**对手文件** 关掉两个向量化器：**+4.382 ms**，
//       ⇒ 向量化器在两代引擎上符号相反，merge 臂已判负）。
// 上述公开提交均未附许可证声明；按本工作区惯例注明账号、原始提交地址与所用内容。
// ======================
// ===== 思路 =====
// ★ 本发为**试验性提交**。目的：**用一次"布局敏感性消融"判掉一个 ★★★ 候选的前置条件**
//   （`BRIEF §2.18.867①`：动任何一段之前，先用消融臂量它的独占占比）。
//
// 【被检验的候选】本 notes §四 候选 1（标 ★★★、从未取点）：
//   "让二级二分不再跨 ~700 KB 的 `VC` 随机取数"，做法是**独立紧凑 side array**。
//
// 【本发的分析（为什么怀疑它的前提）】二级二分的探针值 `VC[cbase+mid]` 与 `VC[cbase+mid+1]`
//   是**同一 piece 内相邻的两个 `VX`（12 B）**，一次探针的 24 B 窗口通常只落在 **1 条** cache line 上。
//   而二分探针的位置是**沿整个 piece 铺开**的 ⇒ **每个探针基本就是 1 条不同的 line**。
//   ⇒ **把元素从 12 B 压到 4 B（例如只查 u32 的 `CH` 秩数组）并不会减少 line 触数**，
//     "紧凑 side array" 只能省字节、省不了行；真正能省的是**探针次数**（而那需要先建块索引，
//     块索引自己的探针又是新增的 line 触数）。**#103949 已经实测过"砍掉约 10% 二级探针"= +2.03 ms（判负）。**
//
// 【本发的判别实验】把 `struct VX` **加一个 4 字节填充**（12 B → 16 B，**成员与语义完全不变**）：
//   * **好处**：每个探针的 24 B 窗口随 `mid` 变成 16 B 对齐 ⇒ 跨两条 line 的探针比例下降；
//   * **代价**：`VC1+VC2` 足迹 **2.4 MB → 3.2 MB**（+800 KB），且每行 64 B 里能装的有效顶点从 5.33 个降到 4 个。
//   ⇒ 若**判题机读数几乎不动**：说明 `VC` 的几何/足迹**不是瓶颈** ⇒ 候选 1 的前提不成立，**直接判掉**；
//     若**明显变慢**：说明足迹/几何**确实在付钱** ⇒ 那条候选值得按"独立紧凑 side array"真做一遍。
//   两种结局都能**关掉一个悬而未决的问题**，而本发**输出与 #105135 逐字节相同**（纯布局改动）。
//
// 单变量：**只把 `struct VX` 的定义加上一个未使用的 `int vxpad;`**，其余一字未动
//   （所有访问都按成员名进行，无 `sizeof(VX)` / 无对 `VX` 的 `memcpy`）。
// 正确性：纯布局改动；仍按规程在本地 17 份**格式合法**的数据上与 #105135 逐字节对拍后才提交。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_260924，提交 #103751 <https://duck.ac/submission/103751>
//     （noi17f 实时榜首，135.829599 ms）。用途：**直接复制**了该提交的完整实现
//     （层=普通数组成链、pieces 合并链、两级二分切线、惰性 peel、SWAR 解析、4 位十进制
//     输出、4 路组相联答案记忆表、`__libc_start_main` 覆盖 + env 扫 `0x6b637564` 取 DuckInfo）。
//     本发只重写它的**输入排序前置段**（见"思路"），查询路径一字未动。
// [2] 本账号（saffah_cc_v41_agg1）在本工作区的提交：#103848 <https://duck.ac/submission/103848>
//     （复刻）、#103956 <https://duck.ac/submission/103956>（文件级 `#pragma GCC target`）、
//     #103966 <https://duck.ac/submission/103966>（去重表 RKT 8 B→u32 打包）。本发以 #103966 为基线。
// [3] ★ **本发的思想直接来自本工作区自己在 noi18a 上兑现过的那把刀**：duck.ac 用户
//     saffah_cc_v41_260924 提交 #99844 <https://duck.ac/submission/99844>（noi18a）
//     引入"融合记录基数排序"——把被排序单位从**下标**改成**记录本身**，使每一趟都变成顺序访存，
//     消掉每元素一次的随机 gather（该刀在两代基底上各实测 −2.09% / −19.7% 的排序相位）。
//     本发把**同一思想**用在 noi17f 的**点排序**上（这里至今仍是"排下标 + `PKEY[src[i]]` 随机取键"），
//     代码为本工作区自行改写，未复制 [3] 的任何一行。
// 上述公开提交均未附许可证声明；按本工作区惯例注明账号、原始提交地址与所用内容。
// ======================
// [4] duck.ac 用户 saffah_cc_v41_260924，提交 #104802 <https://duck.ac/submission/104802>
//     （noi17f 实时榜首，133.032915 ms）。用途：本发**直接采用**该提交相对 #103751 的
//     一个 hunk —— 把切线二分里 `const VX &vy = (mid < pe) ? VC[cbase+mid+1] : VC[nb];`
//     简化为 `const VX &vy = VC[cbase + mid + 1];`，并删掉 `int nb = QPA[pi + 1].cb;`
//     （两个搜索函数 qryl2 / qryr2h 各一份）。该 hunk 的**正确性证明**见本文件"思路"段，
//     由本工作区自行完成，未复制 [4] 的任何一行代码；[4] 亦未给出该简化的理由。
// ======================
// [6] duck.ac 用户 saffah_cc_v41_260924，提交 #104802 <https://duck.ac/submission/104802>
//     （noi17f 实时榜首，133.032915 ms）。用途：本发在它的启发下采用
//     `#pragma GCC optimize("O3","rename-registers","web", ...)` 这一族选项（见"思路"）。
//     本工作区已先对该代码块做过**完备性证明**（本文件同目录 notes.md：`104802` =
//     我们对 #103751 的复刻件 + 恰好 6 个 hunk），并对其中 4 个 hunk 在**我们自己的基底**上
//     逐一用正式提交定价（(c) −0.389 ms ✓ / (a) O3 pragma +2.37 ms ✗ / (b) wr 8 位 +1.07 ms ✗ /
//     (d) 增量哈希 +0.165 ms ✗）。本发**不是**复制它的代码，而是把 (a) 这一族选项**拆开重估**。
// ======================
// [7] 本工作区在本题对"记忆表足迹"的判题机读数：<https://duck.ac/submission/103918>
//     （4 路 x 2^15 -> 4 路 x 2^16，足迹 2 MB -> 4 MB = **+0.99 ms**）。
//     本发走**另一端**：4 路 x 2^14 = **1 MB**。当前最好件见
//     <https://duck.ac/submission/104981>。
// ======================
// ===== 思路 =====
// ★ 试验性提交。目的：给**答案记忆表的足迹**这条轴取另一端。**单变量**：`MWS` 1<<15 → 1<<14。
//
// 【依据】本 notes 记录 #103918（足迹 2 MB → **4 MB**）= **+0.99 ms** ⇒ 足迹每翻一倍约 +1 ms。
//   那么反向减半理论上应 −0.5 ms 量级（缺口 0.44 ms）。旧结论"记忆表这条轴可以永久关闭"
//   是在 **O2 基底**上得出的；按 `§2.18.696` 强形式，换结构（O3 + 关向量化，−1.88 ms）后
//   **整条轴必须重扫**，且**减半这一端从未被取过点**（只取过翻倍那端）。
// 【代价】组数 32768 → 16384，冲突率上升 ⇒ 命中率可能下降（本 notes 记官方命中率约 20%，
//   关掉记忆表值 16.8 ms）。本发就是量这两个反向量谁大。
// 【本发性质】试验性。`MWS` 只影响表大小与索引掩码，语义与答案无关（键仍是完整哈希）。
// ================
// ★ 本发为**试验性提交**。目的：给"`#pragma GCC optimize(..)` 族选项"在我方基底上做一次**拆分定价**。
//
// 【已知事实（全部判题机单变量读数）】
//   * 对手 #104802 相对同一基线的 4 个 hunk 里，`#pragma GCC optimize("O3","rename-registers","web")`
//     在他那儿约值 **−2.1 ms**（他四个 hunk 合计 −2.80 ms），而**同一行放在我方基底上是 +2.37 ms**
//     （#104919 = 136.780991，基线 #104913 = 134.022232）。**同一个 hunk 差 4.5 ms。**
//   * 两者唯一的结构性差别：我方有 `#pragma GCC target("avx2,bmi2,popcnt,sse4.1,ssse3")`，他没有。
//
// 【机理（本地 `g++ -S` 实测，同一份源码只改这一行 pragma）】
//     target only                                      → `hull2` 1948 行，AVX 类指令  41 条
//     + optimize("O3","rename-registers","web")        → `hull2` 2925 行，AVX 类指令 108 条
//     + 追加 "no-tree-vectorize","no-tree-slp-vectorize" → `hull2` 2116 行，AVX 类指令   4 条
//   ⇒ 「胖」与「多出来的 AVX」几乎全部来自**向量化器**；而 `target("avx2",...)` 一旦打开，
//     向量化器就会对**散列探测**这类非连续访问发 AVX2 gather（Coffee Lake 上 gather 是微码的、
//     几十拍一次），同时把热环撑过 µop cache（`§2.18.827`）。
//
// 【本发】保留 O3 的非向量化收益（`rename-registers` / `web` / IPA 等），只**关掉向量化器**。
//   即**单变量**：`#pragma GCC optimize(...)` 的选项集合（一行）。
//   `#pragma GCC target(...)` 保留不动（它单独定价过 −0.664 ms，#103956）。
//
// 【正确性】pragma 不改语义；仍按流程用 `work/brute.cpp` + 9 份大数据做逐字节对拍。
// ================
// 单变量：**删掉两个切线二分里那条已经死掉的 `(mid < pe) ? ... : VC[nb]` 守卫。**
//
// 【为什么它是死的】设 `pe = pp.len - 1`（piece 末顶点在 VC 中的局部下标）、`cbase = pp.cb`。
//   * `while (lo < hi)` 内 `mid = (lo+hi)>>1 < hi <= jhi <= pe` ⇒ **`mid < pe` 恒真**。
//     插桩实测（`.cache/n17f_inst.cpp`，1 754 866 次调用）：`mid >= pe` 出现 **0** 次。
//   * 收尾那一块 `mid = lo`；当 `lo == pe` 时，`if (!(pred)) return pe;` 与随后的
//     `return lo`（此时 `lo == pe`）**返回同一个值** ⇒ **`vy` 取哪一边对结果毫无影响**
//     （插桩实测：`mid == pe` 出现 304 / 1217 次，两种取法的谓词判定差异 **0** 次）。
//   ⇒ `nb`（一次 `QPA[pi+1].cb` 的、可能缺失的 load）与那个三元表达式**纯属开销**：
//     它在访存延迟关键的探针链上每次探针多加一次 cmp + cmov（探针总数 ~4e7 / 1e5 查询）。
//   ⇒ 本改动**可证明是语义保持的**（不是"看起来对"），且不依赖任何测试数据。
//
// 【本发性质】真实提交（非试验）。属"纯减少 uop / 缩短依赖链"类 —— 本 notes 第三节已标定：
// 本引擎上**这一类改动能从本地迁移到判题机**，而"依赖分支预测"类不能。
// ================
// 单变量：**把点排序从"排下标 + 每元素每趟一次随机取键"改成"排融合记录、全部顺序访存"。**
//
// 【问题】原前置段是：
//   `PX[i]/PY[i]` 存坐标，`PKEY[i] = ((u32)(x+1e8)<<32) | (u32)(y+1e8)` 存键，`id[]/tmp[]` 排下标，
//   四趟 16 位基数排序的每一趟都做 **两次 `PKEY[src[i]]` 随机 gather**（计数一次、散播一次），
//   收尾还要按置换做 `XR[r]=PX[p]; YR[r]=PY[p]; NYR[r]=-PY[p];` 的随机取。
//   n = 1e5（判题机 mem ≈ 13 MB，数组按 n 触页 ⇒ n 就是量级上限）⇒ **约 1.6 M 次对 800 KB 表的随机读**
//   + 2e5 次另一次随机取。这一整段是**纯建表、与算法无关**的开销。
//
// 【改法】只留一个融合记录 `struct PR { u32 a, b; u32 p; }`（a = x+1e8，b = y+1e8，p = 原始下标）：
//   * 解析时**一趟写完**记录（原来的"先写 PX/PY 再第二趟算 PKEY"合并掉）；
//   * 四趟基数排序的键由记录里的 a/b 直接取（第 0/1 趟取 b 的低/高 16 位，第 2/3 趟取 a 的低/高 16 位
//     —— 与原 `(PKEY>>shift)&0xFFFF` 逐位同义），**读与写都是顺序的**；
//   * 收尾一趟顺序扫出 `XR/YR/NYR` 与 `RKT[p+1] = r<<15`（只剩 RKT 那一次是按 p 的随机写，不可避免，
//     因为它就是"原始下标 → 秩"的映射本身）。
//   ⇒ `PX/PY/PKEY/id/tmp` 五张表（2.4 MB）整体消失，改成两张记录缓冲（同样 2.4 MB），
//   **但 1.6 M 次随机 gather 变成 0**。别处（含查询路径）一字未动。
// ⚠ 该思想是**本工作区自己在 noi18a 上验证过的**（对边排序用融合记录，两代基底各兑现 −2.09%/−19.7%），
//   出处见 REFERENCES [3]。
// ================
// ===== 思路 =====
// 单变量：**把去重表从 8 B/项压到 4 B/项（800 KB → 400 KB），访问次数不变**。
// 表的语义：`RKT[idx+1]` 给出"原始点 idx 的排序秩"，同时带一个 stamp 做"本查询是否已见过"。
// 打包：`RKT[i] = (rank << 15) | stamp`（rank ≤ n ≤ 1e5 < 2^17，stamp 取 1..32767）。
//   * 探测：`u32 e = RKT[idx+1]; if ((e & 32767u) != CURSTAMP) { RKT[idx+1] = (e & 0xFFFF8000u) | CURSTAMP;
//     DELR[nd++] = (int)(e >> 15); }` —— **一次 load 同时拿到秩与时间戳**，探测次数一字不变。
//   * stamp 每 32767 个查询绕回一次（m ≤ 1e5 ⇒ 3 次）：绕回时做一次**顺序**读改写
//     `for (i = 0..n) RKT[i] &= 0xFFFF8000u`（400 KB 顺序流量，~40 us），**秩在高 17 位不受影响**，
//     所以不需要沿任何置换做随机重写（那才是要避免的）。
//   * 初值 stamp = 0，而 CURSTAMP 从 1 起且绕回后仍 ≥ 1 ⇒ 不需要 `RKT[0]` 那个哨兵项了（顺带删掉）。
// 依据：本 notes 记的同族实测——**"减少触摸字节"必须在"不增加访问次数"的前提下做**
// （#103789 拆表就是因为每点多了一次独立访问而判负 +0.756 ms）。本发正是那个前提下的做法。
// ================
// ===== 思路 =====
// 单变量：在 [1] 的引擎上**只加一行文件级 `#pragma GCC target(...)`**。
// 动机：本工作区在本题的两个**不同世代的基底**上各测过一次文件级 target pragma 都是正的
// （v1 上 −648 us / 0.23%；n7f 基座上 −154 us / 0.10%），而对手这份重写后的引擎**至今没有任何 pragma**
// （`grep pragma` = 0 命中）。本题是纯标量代码（无 SIMD intrinsic），收益应来自指令选择
// （`popcnt`/`bmi2` 的 `bzhi`/`lzcnt` 之类），风险低、量级小，属于"可叠加"的一类。
// 本发除这一行外不改任何东西（连文件头之外的一行代码都没动）。
// ================
// ===== 思路 =====
// 真实提交（非试验）。**本发 = [1] 的逐字节复制 + 两段头注释**，目的是按 `§2.16` 的标准流程
// "复刻对手当代引擎"，先把它变成新基线，再在其上叠刀。
// 口径（`tools/exact.py` 实测，2026-09-28）：我方 138.614553（#103460）vs 对手 #103751 = 135.829599。
// ★ 本发本身**不指望达标** —— 复刻只能把成绩挪到约等于 T（`§2.16.1`：纯复刻必然还差 ~1%），
//   下一发必须在他的引擎上叠一刀。
// ★ 正确性验证：本文件与其原始下载件 `problems/noi17f/ref2/rival_103751.cpp` 逐字节相同（仅加了本头）。
// ================
// NOI2017 分身术 -- agent noi17f_b, pieces (array) implementation.
// Layers are stored as plain arrays of chain vertices; a query maintains the merged
// chain as a list of pieces (contiguous ranges of layer chains). Tangents are found
// by a 2-level binary search (over pieces, then inside a piece) and the merged chain
// is spliced in O(#pieces). The area is computed at the end from prefix sums.
#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 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++; }
  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 cb, len, pf0, pf1; };
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;
  if (VC[QPA[0].cb].rk > 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 PC &pm = QPA[mid];
      const VX &vx = VC[pm.cb + pm.len - 1];
      const VX &vy = VC[QPA[mid + 1].cb];
      i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
      if (vy.rk > k || t > 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.len - 1;
  int jhi = (found >= 0) ? pe : pp.len - 2;
  if (jhi < 0) return pe;
  int cbase = pp.cb;
  int lo = 0, hi = jhi;
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    const VX &vx = VC[cbase + mid];
    const VX &vy = VC[cbase + mid + 1];
    i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
    if (vy.rk > k || t > 0) hi = mid; else lo = mid + 1;
  }
  {
    int mid = lo;
    const VX &vx = VC[cbase + mid];
    const VX &vy = VC[cbase + mid + 1];
    i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
    if (!(vy.rk > k || t > 0)) return pe;
  }
  return lo;
}

// 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 PC &pl = QPA[QNP - 1];
  if (VC[pl.cb + pl.len - 1].rk < k) return -1;
  int found = -1;
  {
    int lo = astart, hi = QNP - 2;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      const PC &pm = QPA[mid];
      const VX &vx = VC[pm.cb + pm.len - 1];
      const VX &vy = VC[QPA[mid + 1].cb];
      i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
      if (vx.rk >= k && t <= 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.len - 1;
  int jhi = (found >= 0) ? pe : pp.len - 2;
  if (jhi < 0) return pe;
  int cbase = pp.cb;
  int lo = 0, hi = jhi;
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    const VX &vx = VC[cbase + mid];
    const VX &vy = VC[cbase + mid + 1];
    i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
    if (vx.rk >= k && t <= 0) hi = mid; else lo = mid + 1;
  }
  {
    int mid = lo;
    const VX &vx = VC[cbase + mid];
    const VX &vy = VC[cbase + mid + 1];
    i64 t = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
    if (!(vx.rk >= k && t <= 0)) return pe;
  }
  return lo;
}

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 pfa = H.PFOF[d] + lo, pfb = H.PFOF[d] + hi;
  if (QNP == 0) { QNP = 1; QPA[0].cb = cb; QPA[0].len = ln; 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].len = offa + 1; QPA[ia].pf1 = pia.pf0 + offa; }
  QPA[hd].cb = cb; QPA[hd].len = ln; QPA[hd].pf0 = pfa; QPA[hd].pf1 = pfb;
  if (ib >= 0) {
    QPA[hd + 1].cb = pib.cb + offb; QPA[hd + 1].len = pib.len - offb;
    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].cb = H.LOF[d0]; QPA[0].len = H.LSZ[d0];
    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];
  for (int q = 0; q + 1 < QNP; q++) {
    const PC &p0 = QPA[q], &p1 = QPA[q + 1];
    const VX &a = H.VC[p0.cb + p0.len - 1];
    const VX &b = H.VC[p1.cb];
    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 = H.VC[p0.cb + p0.len - 1];
    const VX &b = H.VC[p1.cb];
    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;  // odd multiplier: rank -> unique 64-bit key
    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);
  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);
  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;
    u64 hsa = 0x243F6A8885A308D3ULL, hsb = 0x13198A2E03707344ULL;
    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) {
          const int rk = (int)(e >> 15);
          RKT[idx + 1] = (e & 0xFFFF8000u) | CURSTAMP;
          DELR[nd++] = rk;
          const u64 hv = (u64)(u32)rk * 0x2545F4914F6CDD1DULL;
          hsa += hv; hsb ^= hv;
        }
      }
      // 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;
          const u64 hv = (u64)(u32)g * 0x2545F4914F6CDD1DULL;
          hsa += hv; hsb ^= hv;
        }
        DELG[ndg++] = g;
      }
    }
    for (int i = 0; i < ndg; i++) GCUR[DELG[i]] = 0;
    }
    hsa += (u64)nd;
    u64 mh = (hsa * 0x9E3779B97F4A7C15ULL) ^ (hsb * 0xC2B2AE3D27D4EB4FULL);
    mh ^= mh >> 31; if (!mh) mh = 1;
    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 = hull2(h1, DELR, nd, WCNT, WRK);
      i64 a2 = hull2(h2, DELR, nd, WCNT, WRK);
      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

评测结果