代码

/* References: saffah_codex_6a_agg3 https://duck.ac/submission/128577,
deferred answer hashing and unchanged-hull bypass; all inherited sources below.
Idea: Before the first deletion touching either outer hull, only read immutable
membership flags and buffer its original point index. If none is touched, no
rank deduplication or generation-word mutation is needed. On the first affected
point, replay the buffered prefix once through the unchanged deduplicator, then
consume the remaining input normally. The <=100-entry buffer reuses dead DELG.
Purpose: Avoid random generation stores and duplicate tests for provably unchanged
queries while preserving exact first-occurrence deletion order on affected ones.
Stamp rollover, bounded coefficient modular arithmetic, and all hull logic stay. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/128486,
fused point histograms and complete memo/hull engine; unchanged-hull bypass
was explored by our https://duck.ac/submission/121140. Inherited credits below.
Idea: Delay answer-key construction until after all deletions are parsed. If
neither outer hull is touched, return A1C+A2C without computing any per-rank
hash or accessing the answer cache. Otherwise hash the compact DELR sequence
in its original order and use the exact old key and memo algorithm.
Purpose: Unlike the earlier bypass that still hashed every deleted point,
remove rank multiplication/XOR from all unaffected queries and decouple it
from the coefficient-parser/random-rank dependency on affected queries. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/128096,
complete two-hull engine and factored answer hash; inherited authors, public
sources and licenses remain below. Histogram invariance across stable radix
passes is also used in the inherited suffix sorter https://duck.ac/submission/128232.
Idea: While constructing each 56-bit point key, collect all four 14-bit digit
histograms in 16-bit cells. Each pass widens its counts into the original 32-bit
exclusive cursors, avoiding a permutation-dependent key recount. If their sum
is not n, at least one count wrapped by 65536; recount that digit exactly in
32 bits from the unchanged sequential key array. Every lost count is positive,
so this detects every overflow. Scatter order and all geometric logic stay.
Purpose: Delete four indirect histogram traversals and halve count storage
while preserving arbitrary concentrated key distributions through exact fallback. */
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/126925: two-hull bucket preparation and answer memo engine; inherited attribution retained below.
- saffah_codex_6a_agg3, https://duck.ac/submission/126793: original first-hull bucket/memo fusion.
Idea: Accumulate the unweighted rank sum during deletion deduplication, then multiply it once when forming the answer-memo key. Distributivity modulo 2^64 gives exactly the old key, including wrap; the independent XOR hash remains unchanged.
Purpose: Remove one 64-bit multiplication for every unique deleted point, replacing them with one multiplication per query. No key, collision policy, hull or output is changed.
*/
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#126793** <https://duck.ac/submission/126793>
//     （noi17f，103.935446 ms = 本题原 T）—— 本发正文的**底层底盘**（其中 h1 融合刀的字面出处）；
//     其自带的全部继承引用块（#126009 / #125997 / #125984 / #125976 / #125954 / #122407 / #120885 等）
//     **原样保留在下方，一字未删**。该件与下列各件均未声明独立许可证。
// [2] 本账号 **saffah_cc_v41_agg1**：提交 **#126896** <https://duck.ac/submission/126896>
//     （103.704113 ms；**本发正文 = 该提交正文的逐字节副本 + 本席一处改动**，即 [r1noiF2-FUSE] 的
//      h1/h2 单趟融合 + `MWS 1<<14` 原样沿用）、提交 **#126778** <https://duck.ac/submission/126778>
//     （105.382626 ms，#126793 的底盘）、以及 **#122310 / #121989 / #120411**
//     （模归约融合 / 惰性剥离 / 记忆表等刀的字面出处）。
// 合规：按目标原文要求写明「作者账号 / 原始提交地址 / 所用内容」三项；除本引用头、「思路」段与
//     下文所述**一处改动**外，正文一字未改 ✓
// ======================
// ===== 思路 =====
// 【本发 = 本账号 #126896 的逐字节底盘 + 本席一刀 [r1noiF3-HASH2]：删除环逐元素指纹混合 6 条 → 4 条】
//
// 1) 本席前发（#126917）已把本刀单独板面定价：**底盘 #126793 = 103.935446 → #126917 = 103.469186
//    ⇒ [HASH2] = −0.4662 ms（−0.449%）**（同底盘、单一变量）。本发只是把同一把刀叠到本账号当前
//    更好的底盘 #126896（103.704113，含 h1/h2 单趟融合 + MWS 1<<14）之上 ⇒ 期望 ≈ 103.24 ms。
//
// 2) 改动（唯一变量，逐位等价）：删除环里每个被删 rank 原做
//      `xx=(u32)rrk; xx^=xx>>15; xx*=0x2545F4914F6CDD1D; xx^=xx>>29; HSA+=xx; HSB^=xx;`（6 条）
//    改为 `HSA += (u64)(u32)rrk*0x9E3779B97F4A7C15ULL;  HSB ^= (u64)(u32)rrk*0xC2B2AE3D27D4EB4FULL;`（4 条）。
//    ★ 两个常数就是全文自己下游用的同一对（`mh=(sa*K1)^(sb*K2)`）；「xorshift-mul-xorshift」与
//      「一次奇数常量乘」都是双射、逐元素注入强度同级；顺序无关性由**和 + 异或**这两种可交换聚合承担
//      （与原文一致）；`mh` 下游只再混一次、记忆表**逐位比对整键**（k0..k3 == mh）⇒ 指纹口径同构，
//      不引入新的正确性假设。机理依据 = 在册标定「**删除环内每一条指令 ≈ 0.36 核拍/删除 ≈ 0.18 ms 板面**」
//      （n17l_ 的 9 条指令 = −1.53% 即此账），本发去掉 2 条。
//
// 3) 等价性闸门（本机，全部逐字节）：
//    · 生产形 `n17f2_prod.in` md5 **54a81768f627ea2624da4a259195b836** 与底盘同（在册锚点）；
//    · `n17f2_max.in` 4b25c01f5416cf7b804a0e0c8b1e6bb9 · `rc_n17f_prod.in` b766a502d85e2385b1c57e3f31e61c95 ·
//      `rc_n17f_small.in` f34177d1e76a61b96c758332c94136b7 —— 三份全同 ✓；
//    · **暴力 oracle 120 例 0 错**（`work/gen.py` × `work/brute.cpp`：rand/disc/convex/spiral/grid × 8 seeds × k∈{1,3,8}）。
//    （同一闸门在本席前发 #126917 上已全过，且 #126917 板面 Accepted ✓。）
// 4) 目的：真靶 = 严支 `0.99·T+1µs = 102.897092 ms`（现 mine #126917 = 103.469186，缺 0.572 ms = 0.55%）。
//    **本发为真刀提交（非试验性）**；刀口单一变量、已单独板面定价 −0.4662 ms。
// ================
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#126793** <https://duck.ac/submission/126793>
//     用途：**直接复制了该提交的正文**（本发正文 = 该公开件的逐字节副本 + 本席两处改动）。其自带全部
//     REFERENCES/思路 原样保留在下方。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#126881** <https://duck.ac/submission/126881>
//     用途：本席上一发（= [1] 的底盘 + 只把 h2 的 `peel_depth` 换成"层位集直算 `D2`"）。**板面：tc20
//     103.935446 → 104.627350（+0.69 ms，逐点同号）⇒ 单换 h2 不算（扫描趟数没减）**，本发是它的修正版。
// [3] 本账号本席更早两发（**判负留档**）：**#126841**（h1 记忆表对称到 h2 ⇒ +4.94 ms）· **#126856**
//     （删 A1 记忆表 ⇒ +6.42 ms）<https://duck.ac/submission/126841> <https://duck.ac/submission/126856>
//     ⇒ 两条互证：**A1 记忆表承重、h2 侧镜像无收益**。
// [4] `problems/noi17f/notes.md`（`#103903`/`#105135` 记忆表条目、n17k_ 的相位账）。
//     许可证：以上均为 duck.ac 公开提交与公开题面，未见许可证声明；按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【本发 = #126793 底盘 + ① 两半**合并成一趟**的层扫描 + ② MT 表 2 MB→1 MB】
//
// 【为什么上一发（#126881）不够】对手 #126793 的 −1.37 ms 不是"`peel_depth` 慢"，而是**少了一趟扫描**：
//   他把 h1 的层位集扫描与建桶**合成一趟**（`memo_layer[]` + `WRK[L][WCNT[L]++]`），于是原来那次
//   `peel_depth` 的独立扫描被**整趟删掉**。我上一发只把 h2 的 `peel_depth` 换成"另起一趟 `CP2` 扫描 + 位集直算 `D2`"
//   ⇒ **趟数没变**（1 趟换 1 趟），板面 +0.69 ms 证实了这个诊断。
//
// 【本发做什么：真正的对称 —— 一趟同时喂两半】把 h1 那趟改成**融合趟**：对每个被删 rank 同时做
//   ① `CP1[r]` → h1 的 `memo_layer/WRK/WCNT/位集`（与 #126793 一字不差）② `CP2[r]` → h2 的
//   **独立桶集** `WRK2/WCNT2` 与位集 `ma2/mb2`（新增 `WRK2[106][132]` = 56 KB）。
//   h1 段照旧（预建桶 + `D1` + 记忆表两条路）；h2 段变成"由位集直算 `D2` + `hull2d(h2, D2, WCNT2, WRK2)`"，
//   **不再调 `peel_depth`，也不再另起一趟** ⇒ 总扫描趟数 3→2（融合趟 + h1 键趟）。
//   ★ 等价性：`CP2` 与 `CP1` 同构（`peel_init` 写同一个 `H.CP[r]=((cw-LOF[d])<<8)|d`，h2 的 `H.CP` 就是 `CP2`）；
//   `D2` 的语义与 `peel_depth` 的返回值相同（层号全部被盖满 ⇒ 回退原路 `bucket_reset` + `peel_depth` + `hull2d`）；
//   两套桶互不干扰（`hull2d` 消费完自己的桶会在体内自清），`h2` 侧只在 `aff2` 时读写 `WRK2`。
//
// 【刀②】MT 槽数 `1<<15 → 1<<14`（2 MB → 1 MB）：notes 在册判题机单变量 `#105135 = −0.284 ms`、
//   `#105166(→1<<13) = +1.339 ms` ⇒ 极值在 1 MB。键/路数/语义一字不改。
//
// 【闸门】生产形 `rc_n17f_prod.in` md5 **`b766a502d85e2385b1c57e3f31e61c95`** 与底座逐字节同 ·
//   随机闸门 70+35 例（5 形态 × 7 配置）与 `work/o17c_tmp/o17c_brute` **暴力 oracle 0 错**、
//   与底座逐字节相同 · 4+4 例「删除集复现」专项同 · 大件 `n=1e5/m=2e4` convex、grid · `n=5e4/m=3e4` spiral
//   三形态 md5 与底座逐位同（这些形状 h1/h2 同时受影响的比例极高 ⇒ 本刀的新风险面已覆盖）。
//   本机三形状 5 组对照（min-of-3）：convex 78→77 · grid 52→51 · **disc 80→71** · **spiral 49→44**
//   （本机只作否决；上一发它对 h2 单换的符号判对）。
// 【本次为正式提交（非实验）：把"只做了一半的对称刀"做成真正的少一趟扫描。】
// ================
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/126778: current piece/tangent and memo engine, fused coefficient reduction, packed flags and 64-bit chain stack. Its complete attribution follows.
- saffah_codex_6a_agg3, https://duck.ac/submission/125925: the underlying compact outer-flag engine; the full original attribution is restored below as well. These public sources declare no independent license.
Idea: During the existing first-hull memo depth scan, read each packed CP entry once and simultaneously build the deletion-position buckets. Cache its layer in a small query-local array for the memo-key pass. When an already-built deletion-free layer exists, a memo miss consumes these buckets directly instead of rescanning all deletions with peel_depth. A memo hit clears the speculative buckets; if every built layer is affected, clear them before the unchanged lazy-peeling fallback.
Purpose: Eliminate the redundant third deletion scan and its random CP loads while preserving the memo keys, lazy frontier and complete fallback semantics.
*/
/* References: saffah_cc_v41_260924 https://duck.ac/submission/122775,
saffah_codex_6a_agg3 https://duck.ac/submission/125919: compact refreshed engine.
saffah_cc_v41_agg1 https://duck.ac/submission/120840 supplies the outer-layer
unaffected-hull shortcut, inherited by our https://duck.ac/submission/121321;
its packed flag integration was developed from #120589 and our #120479 as
credited in that source. No independent license is declared.
Idea: Adapt the two outer-layer flags to the newer one-sided area memo engine.
Build only the first layers initially, store their membership in the already
loaded deletion word, and skip a half-hull computation when no deleted point
belongs to that outer layer. Preserve the newer A1 memo for affected hulls.
Purpose: Remove memo lookup and layer scan work for provably unchanged halves.
*/
/* References: saffah_cc_v41_260924 https://duck.ac/submission/122775,
saffah_codex_6a_agg3 https://duck.ac/submission/125896: piece/tangent engine,
four-digit parser and 56-bit sorting, copied here with all credits below.
saffah_codex_6a_agg3 https://duck.ac/submission/121321 used packed rank/stamp
words (with the original sources credited below) in the earlier
hull engine; that representation is adapted here without their layer flags.
https://duck.ac/problem/noi17f guarantees distinct points. No separate license.
Idea: Integrate the compact 17-bit rank plus 15-bit generation stamp into the
new piece engine, halving the random-access deletion record. Clear the stamp
bits once per 32767 queries and retain ranks. Distinct-point constraints also
allow direct rank representatives, eliminating duplicate counting, the runtime
branch and inherited duplicate-memory diagnostic writes.
Purpose: Reduce query cache footprint while preserving the new memo engine.
*/
/* References: saffah_cc_v41_260924 https://duck.ac/submission/122775:
copied the current piece/tangent convex-layer engine, preserving its notes.
saffah_codex_6a_agg3 https://duck.ac/submission/121321: reused our accepted
four-digit readers and bounded-coordinate 56-bit radix representation;
its source credits saffah_cc_v41_260924 #117346 and later public piece engines.
https://duck.ac/problem/noi17f provides |coordinate|<=10^8 and c_i<=2^31-1.
No independent source license is declared.
Idea: Integrate the newer piece engine with our four-digit unsigned parser
and 28-bit-per-coordinate sort. Four 14-bit stable passes preserve exactly
the 2D lexicographic order while using 64 KB instead of 256 KB histograms.
The bounded query coefficients never need the signed/64-bit slow path.
Purpose: Reduce parsing dependencies and radix cache pressure together.
*/
// 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.
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125925** <https://duck.ac/submission/125925>
//     用途：**本发正文 = 该提交正文的逐字节副本**（该件自带的继承引用注释块同理逐字保留、
//     位于本文件引用头之后的原位置；本席未改动其中任何被引用内容）。本发在其之上另加下述三把刀：
//     刀 A 模归约融合 · 刀 B mask 整字取用 · 刀 C 单调链栈 STX/STY 扩 64 位，三者均取自 [2]。
//     该件声明「No independent license is declared.」⇒ 无许可证约束，按题面公开可见取用。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#122310** <https://duck.ac/submission/122310>
//     用途：本账号自己的公开最好件；本发三把刀中的 A、B、C 三处**直接复制了该提交的对应代码片段**
//     （模归约融合 / mask 整字取用 / STX-STY 扩 64 位），它们在该件上已被判题机定价为正。
// [3] duck.ac 账号 **saffah_cc_v41_260924**，提交 **#122775** <https://duck.ac/submission/122775>
//     用途：经 [1] 的继承链到达本发的 piece/tangent 引擎与 A1 记忆表；本席未直接引用，仅随 [1] 继承。
// ======================
// ===== 思路 =====
// 【本发 = 对手 #125925 的逐字节底盘 + 我账号 #122310 已被判题机定价为正的三把刀，全部语义逐位等价。】
// 本席先做剂量判定（这一步决定了本发只押哪几刀）：
//  · 用 -DVERIFY + 计数探针在 n=m=1e5 生产形上实测底盘：A1 记忆表命中 HIT1=34 / MISS1=96623 / FB1=1
//    ⇒ 对手的记忆表在**本席代理数据上几乎不命中**（键 = 「h1 层号 < D1 的被删点集合」，随机数据下不重复）。
//    这推翻「记忆表本身是净收益」的直觉，也解释了逐测试点为何在 k=1/2 的 tc5~tc12 上我方旧件反而快
//    ~1.0~1.8 ms（记忆表是每查询固定开销）而在大 k 的 tc15~tc20 上被对手反超（官方数据的删除集集中，
//    记忆表在那里命中）。⇒ **本发不碰记忆表结构，只把它自己漏掉的三把"纯减法"刀补回去。**
// 刀 A（模归约融合，直接复制 #122310）：原式先对 cv 做 fastmod 得 rr∈(-n,n)、修符号，再与 Smod 相加二次修；
//   改 `uu=Smod+cv`（uu<2^31+1e5<2^32 安全）后对 uu 做同一 fastmod ⇒ **只修一次**。证明：M=ceil(2^32/n)、
//   nM=2^32+a（a∈[0,n)）⇒ uM/2^32 = q+qa/2^32+rM/2^32，两尾项各 <1 ⇒ 小数部分 <2 ⇒ qq∈{⌊u/n⌋,⌊u/n⌋+1}
//   ⇒ u-qq·n∈(-n,n)。数值闸门 fmchk 18,570,000 例 0 错（含 u→2^32 边界）；gcc9 `.s` 该段 20→11 条指令。
// 刀 B（mask 整字取用，直接复制 #122310）：`mask |= (e>>13)&3u` → `mask |= e`（e 即 RKT 字，位 13/14 就是
//   两个层-1 标志），门控判据同步改 `0x2000u`/`0x4000u`，语义全同、每删除省 2 条移位/与。
// 刀 C（STX/STY 扩 64 位，直接复制 #121989→#122310 的刀）：单调链栈存的是 |坐标|≤1e8 的原值，
//   原码在 peel 的叉积处每次生成 4 条 32→64 位符号扩展；扩宽后符号扩展全消、算术一字不改（代价 +1.6 MB 常驻）。
// 定价依据：刀 A+B+C 在 #121989→#122310 上被判题机实测 −1.53%（tc16 −1.61% / tc17 −1.64% / tc18 −1.77% /
//   tc19 −1.32% / tc20 −1.53%，全线同号）；判题机 5 臂梯给 M(③②①) = −0.81%（vs A 臂，仪器带宽 ±0.1%）。
// 【目的 = 达标】：把对手的 T 件底盘与我方已定价的减法刀合体，目标 ≤ 0.99*T+1µs = 106.043120 ms。
// 闸门：生产形 n=m=1e5 与 #125925 **逐字节相同**（md5 54a81768f627ea2624da4a259195b836）+ 合法域随机
//   多形态暴力 oracle 0 错 + 判题机 gcc9.3 复编通过。本次为实发件，非试验件。
// ================
#include <cstdint>
#include <cstring>
#include <emmintrin.h>

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

#pragma GCC target("bmi,bmi2")
#pragma GCC optimize("O3","rename-registers","web","ipa-pta","inline-functions","align-jumps=16","align-loops=16:12","align-functions=64")
static const int MAXN = 100005;
static const int MAXL = 104;
static const int MAXDEL = 128;
static const int MAXP = 600;

static int PX[MAXN], PY[MAXN];
static int XR[MAXN], YR[MAXN], NYR[MAXN];
static u64 PKEY[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() {
 const u8*p=gip;while(*p<=32)++p;u32 v=0;
 for(;;){u32 w;memcpy(&w,p,4);if((w&0xf0f0f0f0u)!=0x30303030u)break;
 w&=0x0f0f0f0fu;w=(w*10u+(w>>8))&0x00ff00ffu;
 v=v*10000u+((w*100u+(w>>16))&65535u);p+=4;}
 while(*p>32)v=v*10u+(u32)(*p++-'0');
 gip=p+1;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) {
  const u8 *p=gip;while(*p<=32)++p;
  u32 v=0;
  for(;;){u32 w;memcpy(&w,p,4);if((w&0xf0f0f0f0u)!=0x30303030u)break;
    w&=0x0f0f0f0fu;w=(w*10u+(w>>8))&0x00ff00ffu;
    v=v*10000u+((w*100u+(w>>16))&65535u);p+=4;}
  while(*p>32){v=v*10u+(u32)(*p++-'0');}
  gip=p+1;v32=v;slow=0;return 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 >= 100000000ULL) {
    u32 r = (u32)(x % 100000000ULL); x /= 100000000ULL;
    u32 r1 = r / 10000u, r2 = r - r1 * 10000u;
    u32 r3 = r1 % 100u; r1 /= 100u; u32 r4 = r2 % 100u; r2 /= 100u;
    o -= 8; memcpy(o, HEXD + r1 * 2, 2); memcpy(o + 2, HEXD + r3 * 2, 2);
    memcpy(o + 4, HEXD + r2 * 2, 2); memcpy(o + 6, HEXD + r4 * 2, 2); }
  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; };
struct __attribute__((aligned(32))) EDG { i64 c0; int rk, nrk, c1, c2, pad0, pad1; };
static VX   VC1[MAXN + 8], VC2[MAXN + 8];
static EDG  EG1[MAXN + 8], EG2[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
  EDG *EG;        // CQ2: per-chain-edge precomputed tangent constants (see mk_eg.py)
  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 u8 LAY1[MAXN], LAY2[MAXN];
static int ST[MAXN]; static long long 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] = (long long)xi; STY[tp] = (long long)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 (H.TAG == 1) LAY1[r] = (u8)d; else LAY2[r] = (u8)d; }
  { /* CQ2: precompute the edge constants once per chain vertex. */
    EDG *eg = H.EG + H.LOF[d];
    const VX *vc = H.VC + H.LOF[d];
    int m = H.LSZ[d];
    for (int i = 0; i + 1 < m; i++) {
      int ax = vc[i].x, ay = vc[i].y, bx = vc[i + 1].x, by = vc[i + 1].y;
      eg[i].c0 = (i64)ax * (i64)by - (i64)ay * (i64)bx;
      eg[i].c1 = ay - by;
      eg[i].c2 = bx - ax;
      eg[i].rk = vc[i].rk; eg[i].nrk = vc[i + 1].rk;
    }
    if (m > 0) { eg[m - 1].c0 = 0; eg[m - 1].c1 = 0; eg[m - 1].c2 = 0;
                 eg[m - 1].rk = vc[m - 1].rk; eg[m - 1].nrk = 0; }
  }
  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;
}

static const u32 *G_CP2;   // m19 port of lane BY4's cross-hull CP prefetch target
// 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];

// ---- m137 NSORT: branchless compare-exchange network for the bucket sort.
// Verified exhaustively (all permutations, n = 2..8, 0 failures) by
// work/.tmp/netcheck.  CX is a cmov pair: no branch, so the bucket size d
// stops being a mispredict source.
#define CX(a, b) do { int t0 = W[a], t1 = W[b]; int mm = (t0 > t1); W[a] = mm ? t1 : t0; W[b] = mm ? t0 : t1; } while (0)
static void sortW(int *W, int d) {
  switch (d) {
    case 8: CX(0,1);CX(2,3);CX(4,5);CX(6,7);CX(0,2);CX(1,3);CX(4,6);CX(5,7);CX(1,2);CX(5,6);CX(0,4);CX(3,7);CX(1,5);CX(2,6);CX(1,4);CX(3,6);CX(2,4);CX(3,5);CX(3,4); return;
    case 7: CX(1,2);CX(3,4);CX(5,6);CX(0,2);CX(3,5);CX(4,6);CX(0,1);CX(4,5);CX(2,6);CX(0,4);CX(1,5);CX(0,3);CX(2,5);CX(1,3);CX(2,4);CX(2,3); return;
    case 6: CX(1,2);CX(4,5);CX(0,2);CX(3,5);CX(0,1);CX(3,4);CX(2,5);CX(0,3);CX(1,4);CX(2,4);CX(1,3);CX(2,3); return;
    case 5: CX(0,1);CX(3,4);CX(2,4);CX(2,3);CX(1,4);CX(0,3);CX(0,2);CX(1,3);CX(1,2); return;
    case 4: CX(0,1);CX(2,3);CX(0,2);CX(1,3);CX(1,2); return;
    case 3: CX(1,2);CX(0,2);CX(0,1); return;
    case 2: CX(0,1); return;
    default: return;
  }
}

// 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;
    { const int LEAD = 8;
      int zn = nd - LEAD; if (zn < 0) zn = 0;
      for (int z = 0; z < zn; z++) { __builtin_prefetch(cp + del[z + LEAD], 0, 1); int x = del[z]; unsigned c = cp[x] & 255u; if (c - 1u < 8u) m |= 1u << c; wrk[c][wcnt[c]++] = (int)(cp[x] >> 8); }
      for (int z = zn; 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) { found = mid; hi = mid - 1; }
      else {
        { __asm__ volatile("" :: "m"(*(const VX *)&vx), "m"(*(const VX *)&vy)); }
        i64 t2 = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
        if (t2 > 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 nb = QPA[pi + 1].cb;
  int lo = 0, hi = jhi;
  int hit = 0;                          // m173 VCHK: did the predicate ever hold?
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    const EDG &e = H.EG[cbase + mid];
    i64 t = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
    if (e.nrk > k) { hi = mid; hit = 1; }
    else {
      { __asm__ volatile("" :: "m"(*(const EDG *)&e)); }
      i64 t2 = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
      if (t2 > 0) { hi = mid; hit = 1; } else lo = mid + 1;
    }
  }
  if (!hit) {                           // only reachable with lo == jhi (see the header note)
    int mid = lo;
    if (mid < pe) {                     // EDG form: EG[cbase+mid] was just probed (L1), and
      const EDG &e = H.EG[cbase + mid]; // e.rk==vx.rk, e.nrk==vy.rk, c0+kx*c1+ky*c2 == cross
      i64 t = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
      if (!(e.nrk > k || t > 0)) return pe;
    } else {
      const VX &vx = VC[cbase + mid];
      const VX &vy = (mid < pe) ? VC[cbase + mid + 1] : VC[nb];
      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) { lo = mid + 1; }
      else {
        { __asm__ volatile("" :: "m"(*(const VX *)&vx), "m"(*(const VX *)&vy)); }
        i64 t2 = (i64)(vx.x - kx) * (vy.y - ky) - (i64)(vx.y - ky) * (vy.x - kx);
        if (t2 <= 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 nb = QPA[pi + 1].cb;
  int lo = 0, hi = jhi;
  int hit = 0;                          // m173 VCHK
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    const EDG &e = H.EG[cbase + mid];
    i64 t = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
    if (e.rk < k) { lo = mid + 1; }
    else {
      { __asm__ volatile("" :: "m"(*(const EDG *)&e)); }
      i64 t2 = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
      if (t2 <= 0) { hi = mid; hit = 1; } else lo = mid + 1;
    }
  }
  if (!hit) {
    int mid = lo;
    if (mid < pe) {                     // EDG form (see qryl2)
      const EDG &e = H.EG[cbase + mid];
      i64 t = e.c0 + (i64)kx * (i64)e.c1 + (i64)ky * (i64)e.c2;
      if (!(e.rk >= k && t <= 0)) return pe;
    } else {
      const VX &vx = VC[cbase + mid];
      const VX &vy = (mid < pe) ? VC[cbase + mid + 1] : VC[nb];
      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) {
  /* m161i PURE: `if (lo > hi) return;` removed -- BOTH callers guard `cur < L` / `cur < sz`,
     so lo <= hi at every call (proved in mk_pure.py); `ins2` has no other caller. */
  int cb = H.LOF[d] + lo, ln = hi - lo + 1;
  int pfa = H.PFOF[d] + lo, pfb = H.PFOF[d] + hi;
  /* m161i PURE: the `QNP == 0` early branch removed.  On that path the searches return -1
     (their own guards, which gcc must now emit again), so ia = ib = -1, hd = 0, nt = 0, and
     the splice writes EXACTLY the same QPA[0] and QNP = 1 that the branch wrote. */
  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) {
    // FIXED-COUNT, DIRECTION-FREE splice tail move.
    // The shipped form needs a DESCENDING copy when dst > src and an ASCENDING one
    // otherwise, because an in-place shift of 16-byte records overwrites its own
    // source for one of the two signs -- the direction test is not removable by
    // itself.  Issuing EVERY load before ANY store removes the direction entirely:
    // both shifts become one straight-line block, with no data-dependent branch and
    // no variable-trip loop exit left to mispredict.
    // Entries [src+8, ...) that are read are written only into slots [dst+nt, ...],
    // and QNP_new == dst + nt, so those slots are outside the live chain: the extra
    // read-modify is harmless.  QNP <= 17 in every firing count on record, so the
    // scalar fallback below is the tail we do not pay for.
    const int src = ib + 1;
    if (nt <= 8) {
        __m128i v0 = _mm_loadu_si128((const __m128i *)(QPA + src));
        __m128i v1 = _mm_loadu_si128((const __m128i *)(QPA + src + 1));
        __m128i v2 = _mm_loadu_si128((const __m128i *)(QPA + src + 2));
        __m128i v3 = _mm_loadu_si128((const __m128i *)(QPA + src + 3));
        __m128i v4 = _mm_loadu_si128((const __m128i *)(QPA + src + 4));
        __m128i v5 = _mm_loadu_si128((const __m128i *)(QPA + src + 5));
        __m128i v6 = _mm_loadu_si128((const __m128i *)(QPA + src + 6));
        __m128i v7 = _mm_loadu_si128((const __m128i *)(QPA + src + 7));
        _mm_storeu_si128((__m128i *)(QPA + dst), v0);
        _mm_storeu_si128((__m128i *)(QPA + dst + 1), v1);
        _mm_storeu_si128((__m128i *)(QPA + dst + 2), v2);
        _mm_storeu_si128((__m128i *)(QPA + dst + 3), v3);
        _mm_storeu_si128((__m128i *)(QPA + dst + 4), v4);
        _mm_storeu_si128((__m128i *)(QPA + dst + 5), v5);
        _mm_storeu_si128((__m128i *)(QPA + dst + 6), v6);
        _mm_storeu_si128((__m128i *)(QPA + dst + 7), v7);
    } else {
      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;
}

// ---- f17c_rv `a1m`: hull2 split so the caller may reuse a peel_depth result and, on a memo
// hit, skip the splice+area entirely.  `hull2d` is the ORIGINAL body with `i` supplied.
static void bucket_reset(LYS &H, int *wcnt) {
  int hi = H.NL; if (hi > 101) hi = 101; for (int c2 = 0; c2 <= hi; c2++) wcnt[c2] = 0;
}
static i64 hull2d(LYS &H, int D, int *wcnt, int (*wrk)[MAXDEL + 4]) {
  int i = D - 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];
      if (d <= 8) sortW(W, d);
      else 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.
  bucket_reset(H, wcnt);
  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 WCNT2[MAXL + 2];
static int WRK[MAXL + 2][MAXDEL + 4];
static int WRK2[MAXL + 2][MAXDEL + 4];
static u32 RKT[MAXN + 1];
static u32 CURSTAMP;
static int DELR[MAXDEL], DELG[MAXDEL];

static LYS h1, h2;

// ------------------------------------------------------------------ f17c_rv a1 memo
// Key = the SET of deleted h1-chain vertices, as (layer,pos) = CP1[r].  Order-independent.
// 2-way set associative, 2^15 slots.  `A1V[..]` holds a1.
#define A1BITS 15
#define A1N (1 << A1BITS)
static u64 A1KA[2][A1N], A1KB[2][A1N];
static i64 A1V[2][A1N];
#ifdef VERIFY
#include <cstdio>
#endif
static long long VMM;
static long long CNT_FB1, CNT_HIT1, CNT_MISS1;
static inline u64 mix64(u64 x) { x ^= x >> 15; x *= 0x2545F4914F6CDD1DULL; x ^= x >> 29; return x; }


// ------------------------------------------------------------------ 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;
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 ^= x >> 15; x *= 0x2545F4914F6CDD1DULL; x ^= x >> 29;
    sa += x; sb ^= x;
  }
  u64 h = (sa * 0x9E3779B97F4A7C15ULL) ^ (sb * 0xC2B2AE3D27D4EB4FULL);
  h ^= h >> 31; if (!h) h = 1;
  return h;
}

static u64 HSA, HSB;
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();
  for (int i = 0; i < n; i++) { PX[i] = (int)rdi64(); PY[i] = (int)rdi64(); }
  static unsigned short key_hist[4][1 << 14];
  memset(key_hist, 0, sizeof key_hist);
  for (int i = 0; i < n; i++) {
    u64 key = ((u64)(u32)(PX[i] + 100000000) << 28) | (u64)(u32)(PY[i] + 100000000);
    PKEY[i] = key;
    key_hist[0][key & 0x3fffu]++;
    key_hist[1][(key >> 14) & 0x3fffu]++;
    key_hist[2][(key >> 28) & 0x3fffu]++;
    key_hist[3][key >> 42]++;
  }
  static int id[MAXN], tmp[MAXN];
  for (int i = 0; i < n; i++) id[i] = i;
  {
    static int cnt[1 << 14];
    int *src = id, *dst = tmp;
    for (int pass = 0; pass < 4; pass++) {
      int shift = pass * 14;
      int sum = 0;
      for (int i = 0; i < (1 << 14); i++) { int c = key_hist[pass][i]; cnt[i] = sum; sum += c; }
      if (sum != n) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(int)((PKEY[i] >> shift) & 0x3FFF)]++;
        sum = 0;
        for (int i = 0; i < (1 << 14); i++) { int c = cnt[i]; cnt[i] = sum; sum += c; }
      }
      for (int i = 0; i < n; i++) { int p = src[i]; dst[cnt[(int)((PKEY[p] >> shift) & 0x3FFF)]++] = p; }
      int *t = src; src = dst; dst = t;
    }
    if (src != id) memcpy(id, src, sizeof(int) * (size_t)n);
  }
  for (int r = 1; r <= n; r++) { int p = id[r - 1]; XR[r] = PX[p]; YR[r] = PY[p]; NYR[r] = -PY[p]; RKT[p + 1] = (u32)r<<15; }
  static int GREP[MAXN], GCNT[MAXN], GCUR[MAXN], REPL[MAXN];
  RKT[0]=0;int nrep=n;for(int r=1;r<=n;r++)REPL[r]=r;
  h1.N = n; h1.X = XR; h1.Y = YR; h1.CH = CHP1; h1.VC = VC1; h1.EG = EG1; 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.EG = EG2; 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,1);peel_to(h2,1);
  for(int j=0;j<h1.LSZ[1];j++)RKT[id[h1.CH[h1.LOF[1]+j]-1]+1]|=1u<<13;
  for(int j=0;j<h2.LSZ[1];j++)RKT[id[h2.CH[h2.LOF[1]+j]-1]+1]|=1u<<14;
  const i64 A1C=hull2d(h1,1,WCNT,WRK),A2C=hull2d(h2,1,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 = 1;
  for (int step = 0; step < m; step++) {
    int k = (int)rdu32();
    if(++CURSTAMP==8192){
      for(int i=1;i<=n;i++)RKT[i]&=0xffffe000u;
      CURSTAMP=1;
    }
    int nd = 0, ndg = 0;u32 mask=0;
    if (NODUP) {
      auto read_index = [&]() __attribute__((always_inline)) {
        u64 bigv; int slow;
        u32 cv = rdc(bigv, slow);
        u32 uu = Smod + cv;
        u32 qq = (u32)((NM * (u64)uu) >> 32);
        int rr = (int)(uu - qq * (u32)n);
        if (rr < 0) rr += (int)n;
        return rr;
      };
      auto record_index = [&](int idx) __attribute__((always_inline)) {
        u32 e = RKT[idx + 1];
        if ((e & 8191u) != CURSTAMP) {
          RKT[idx+1]=(e & 0xffffe000u)|CURSTAMP;
          DELR[nd++] = (int)(e>>15); mask |= e;
        }
      };
      int i = 0; bool affected = false;
      for (; i < k; i++) {
        int idx = read_index(); DELG[i] = idx;
        if (RKT[idx+1] & 0x6000u) { affected = true; ++i; break; }
      }
      if (affected) {
        for (int z = 0; z < i; z++) record_index(DELG[z]);
        for (; i < k; i++) record_index(read_index());
      }
      // 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 & 8191u) != CURSTAMP) {
        RKT[idx+1]=(e & 0xffffe000u)|CURSTAMP;
        int g = GREP[rk];
        if (++GCUR[g] == GCNT[g]) DELR[nd++] = g;
        DELG[ndg++] = g;
      }
    }
    for (int i = 0; i < ndg; i++) GCUR[DELG[i]] = 0;
    }
    if (!(mask & 0x6000u)) {
      S = A1C + A2C;
    } else {
      HSA = 0; HSB = 0x13198A2E03707344ULL;
      for (int z = 0; z < nd; z++) {
        u32 rank = (u32)DELR[z];
        HSA += rank;
        HSB ^= (u64)rank * 0xC2B2AE3D27D4EB4FULL;
      }
    u64 mh;
    { u64 sa = 0x243F6A8885A308D3ULL + HSA * 0x9E3779B97F4A7C15ULL + (u64)nd, sb = HSB;
      u64 h = (sa * 0x9E3779B97F4A7C15ULL) ^ (sb * 0xC2B2AE3D27D4EB4FULL);
      h ^= h >> 31; if (!h) h = 1; mh = h; }
    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 {
      const int aff1 = (mask & 0x2000u) != 0;
      const int aff2 = (mask & 0x4000u) != 0;
      u64 ma = 0, mb = 0, ma2 = 0, mb2 = 0;
      u8 memo_layer[MAXDEL];
      if (aff1 | aff2) {
        for (int z = 0; z < nd; z++) {
          int r = DELR[z];
          if (aff1) { u32 cp = CP1[r], L = cp & 255u;
            memo_layer[z] = (u8)L; WRK[L][WCNT[L]++] = (int)(cp >> 8);
            if (L) { if (L <= 64) ma |= 1ull << (L - 1); else mb |= 1ull << (L - 65); } }
          if (aff2) { u32 cp = CP2[r], L = cp & 255u;
            WRK2[L][WCNT2[L]++] = (int)(cp >> 8);
            if (L) { if (L <= 64) ma2 |= 1ull << (L - 1); else mb2 |= 1ull << (L - 65); } }
        }
      }
      i64 a1;
      if(!aff1)a1=A1C;else {
        u64 ka = 0, kb = 0;
        int D1 = 0;
        { int NL = h1.NL; if (NL > 101) NL = 101;
          u64 fa = (NL >= 64) ? ~0ull : ((1ull << NL) - 1);
          u64 fb = (NL > 64) ? ((1ull << (NL - 64)) - 1) : 0;
          if (ma == fa && mb == fb) {                    // all layers covered -> D > NL
            CNT_FB1++;
            bucket_reset(h1, WCNT);
            int DD = peel_depth(h1, DELR, nd, WCNT, WRK);
            a1 = hull2d(h1, DD, WCNT, WRK);
            goto a1_done;                                // no memo: key not trustworthy
          }
          D1 = (ma != fa) ? (__builtin_ctzll((~ma) & fa) + 1)
                          : (64 + __builtin_ctzll((~mb) & fb) + 1); }
        for (int z = 0; z < nd; z++) { u32 L = memo_layer[z];
          if (L && (int)L < D1) { u64 x = mix64((u64)DELR[z]); ka += x; kb ^= x; } }
        ka += 0x9E3779B97F4A7C15ULL; kb ^= 0xD1B54A32D192ED03ULL;
        u64 hh = (ka * 0x9E3779B97F4A7C15ULL) ^ (kb * 0xC2B2AE3D27D4EB4FULL);
        hh ^= hh >> 31;
        int sl = (int)(hh >> (64 - A1BITS));
        int w = (A1KA[0][sl] == ka && A1KB[0][sl] == kb) ? 0
              : (A1KA[1][sl] == ka && A1KB[1][sl] == kb) ? 1 : -1;
        if (w >= 0) { a1 = A1V[w][sl];
          bucket_reset(h1, WCNT);
#ifdef VERIFY
          { int DD = peel_depth(h1, DELR, nd, WCNT, WRK);
            i64 tru = hull2d(h1, DD, WCNT, WRK);
            if (tru != a1) { VMM++; if (VMM < 6) printf("MM %lld %lld ka=%llu kb=%llu nd=%d NL=%d\n",(long long)a1,(long long)tru,ka,kb,nd,h1.NL); } }
#endif
        }
        else {
          CNT_MISS1++;
          a1 = hull2d(h1, D1, WCNT, WRK);
          A1KA[1][sl] = A1KA[0][sl]; A1KB[1][sl] = A1KB[0][sl]; A1V[1][sl] = A1V[0][sl];
          A1KA[0][sl] = ka; A1KB[0][sl] = kb; A1V[0][sl] = a1;
        }
      }
    a1_done:;
#ifdef VERIFY
    if (VMM) { static int once=1; if(once){once=0; printf("VERIFY MISMATCHES %lld\n", VMM);} }
#endif
      i64 a2;
      if(!aff2)a2=A2C;else {
        int D2 = 0;
        { int NL = h2.NL; if (NL > 101) NL = 101;
          u64 fa = (NL >= 64) ? ~0ull : ((1ull << NL) - 1);
          u64 fb = (NL > 64) ? ((1ull << (NL - 64)) - 1) : 0;
          if (ma2 == fa && mb2 == fb) {
            bucket_reset(h2, WCNT2);
            int DD = peel_depth(h2, DELR, nd, WCNT2, WRK2);
            a2 = hull2d(h2, DD, WCNT2, WRK2);
            goto a2_done;
          }
          D2 = (ma2 != fa) ? (__builtin_ctzll((~ma2) & fa) + 1)
                           : (64 + __builtin_ctzll((~mb2) & fb) + 1); }
        a2 = hull2d(h2, D2, WCNT2, WRK2);
      }
    a2_done:;
      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

评测结果