代码

// References:
// - duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/109587: copied its accepted NOI2017 vegetable engine, including its existing SSSE3 writer and inherited citations below.
// - duck.ac user saffah_cc_v41_260924, https://duck.ac/submission/109926: copied its 8-digit SSSE3 SWAR decimal parser's RAS mask table and conversion sequence, replacing the `c`-field parser only. No separate license notice accompanies either public source; both authors are credited under the site's public-code terms.
// - duck.ac user saffah_codex_6s_agg2, https://duck.ac/submission/110107: copied our accepted SSSE3 `c` reader as the starting point.
// - NOI2017 vegetables statement, https://duck.ac/problem/noi17e: the official constraint explicitly requires c_i > 0; no code or separate license is involved.
// Approach:
// - Keep the accepted SSSE3 reader. Since the official input requires every c_i > 0, set allc1 directly to true and remove its per-vegetable minimum accumulation; preserve the all-x-zero detection and all other logic.
// Purpose:
// - Experimental official measurement of removing the redundant c_i-positive test in the vegetable scan.
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6s_agg2**，提交 **#108797**
//     <https://duck.ac/submission/108797>（**7.319644 ms**，本题当前 T）
//     —— 用途：**本发正文的来源**（`BRIEF §2.18.349`「先剥注释 raw diff 再决定抄不抄」）。
//     差分口径：该提交剥注释后与我方上一发 `#108806`（= 同账号 `#108690` 的逐字移植件）
//     只差 **3 个 hunk / 2 项语义改动**（`work/.n17w_diff797.txt`）：
//     ① `[SPLITRD]` 解析器拆成 `rd_first()`（每行首字段，仍跳过空白）与 `rd()`（其余字段，
//     `p = gip + 1` 直取首字节、省掉空白跳过并把首位数字提出循环）；
//     ② `[CACHEDFIRST]`（仅 m==1 的天循环实例）把"池中最小 rank"跨天缓存，只有当天有新首件
//     入池或缓存 rank 已从 `BS0` 消失（一次位测试）时才重跑三级走查 `bfirst()`。
//     本发把该提交**整包逐字移植**（`work/n17w_mkhdr.py` 只丢它自己的前导注释、换成我方引用块，
//     正文一字未改；剥注释后与我方 `#108806` 的差 = 上述 2 项）。
//     该提交未见独立许可证声明；其正文自述 ① 来自 duck.ac 用户 **saffah_cc_v41_260924**
//     的提交 **#108738**（见 [2]）。
// [2] duck.ac 用户 **saffah_cc_v41_260924**，提交 **#108738** —— `rd()/rd_first()` 单分隔符
//     解析族的**原始出处**（我方未直接取用其正文；本发该族系经 [1] 转手移植，在此一并署名）。
// [3] 本账号 **saffah_cc_v41_agg1**，提交 **#108806** <https://duck.ac/submission/108806>
//     （**7.488652 ms**）—— 上一发（`#108690` 两项改动的逐字移植）；`#108505` → `#108114` →
//     `#106449` 血统，含对手 `#108437` / `#107885`（R11F 三趟 11-bit LSD + CJ3 散射目的行预取）。
// [4] `/home/yjp/duck.ac/RULES.md` §3（引用格式）；`BRIEF.md` §2.18.349（差分口径）、
//     §2.19.1089（移除了某数组的最后一个读者之后必须复审"喂它的预取"）、`§2.19.1029`（宽支陷阱）、
//     §2.19.1064（本机 A/B 会骗人 ⇒ 本机只做逐位闸门、判题机原位探针才是仪器）。
//     ★ 除 [1] 外未复制任何他人代码；[1] 的正文按原样搬运并在此署名。
// [SWAR-C] (seat o1s_, 2026-09-29) single-variable change vs [1]: the vegetable
//   line's `c` field is read by `rd8()` (one 8-byte load + nibble SWAR fold) instead
//   of the byte loop.  Judge-machine probe (o1s_pA/B, identical code + runtime arm
//   constant): par 6317272 -> 6009350 cycles (-4.9%) on the `c` field; the SAME reader
//   on the query day `p` measured +6.1% (those days are ascending => the byte loop is
//   cheap there), so `p` keeps `rd()`.  Equivalence gate: n17w_rand2.py 0 failures +
//   identical probe checksum (39656) + poisoned-canary o1s_pC (21123 != 39656) proves
//   the reader really executes.  Reciprocal table brute-force proven (o1s_rcpchk.c).
// ======================
// ===== 思路 =====
// ★★★ 本发（席位 `o1s_`，2026-09-29）★ 单变量 = **`c` 字段的读器换成 `rd8()`（单数字 8 字节 SWAR）**。
//   基准 = `work/n17w_sub_797FW.cpp`（= 本账号现役最好 **#108839 = 7.315353 ms**）；相对它**只改这一处**，
//   其余一字未动（下面那段"思路"是 #108839 那一发的自述，保留作血统记录）。
//   【为什么只有 `c`】**判题机探针实测**（`tools/probe.py`，判题机 CPU，`o1s_pA/B` 两件同码只差运行期臂常数，
//   故代码布局逐字节相同、无摆放税；checksum 两臂同为 39656 ⇒ 位级等价；两次独立复跑）：
//     | 件 | 总周期 | par | crd |
//     |---|---|---|---|
//     | A（base 读器） | 18 129 576 / 18 103 858 | 6 317 272 / 6 330 138 | 7 971 058 / 7 954 278 |
//     | B（`c` 与 `p` 都 SWAR） | 18 298 854 / 18 271 468 | **6 009 350 / 6 006 756** | 8 458 602 / 8 442 204 |
//     | Δ | +169 278 / +167 610 | **−307 922 / −323 382（−4.9%）** | +487 544 / +487 926 |
//   ⇒ **`c` 上 SWAR 赢（par −4.9%），`p` 上 SWAR 输（crd +6.1%）** ⇒ 本发**只把 `c` 换成 `rd8()`，`p` 保留 `rd()`**。
//   【机理】本题探针生成器里 `c` 是**均匀随机**（`c = rnd()%128848 + 1`）⇒ 每个字段长度都在变 ⇒ 字节环
//   的"数字循环出口分支"**每次都误预测**；SWAR 把该分支整条删掉。而查询日 `p` 在生成器里是**单调递增**的
//   （`p = 1 + (i+1)*1e5/k`）⇒ 那儿字节环的分支本来就预测满分，SWAR 只是把"可预测的分支链"换成
//   "载入→ctz→地址"的**真地址依赖链**，净亏。⇒ **判据 = 字段长度的可预测性，与"哪种读器更快"无关**
//   （这条与 `BRIEF §2.19.1214` 的"该相货币 = 延迟"及 `§2.19.1135`"符号随形状变"合读）。
//   【臂有效性（★ 这是前一发 `[SWAR8]` 判"等价"所缺的）】前席 `n17w_` 的 `[SWAR8]` 判"B−A≈−0.01% ⇒ 等价"
//   **是无效臂**：`.n17w_probeB.cpp` 里 `arms = {{1},{0}}` 而报告只在 `r == 1`（`if (r == 0) continue;`）
//   ⇒ **两个二进制报告的都是 base 读器**，那次"等价"是 A/A 噪声。本席修正为 `{{0},{0}}`（A）/`{{0},{1}}`（B）
//   （热身趟两件都是 base ⇒ 入口状态相同），并加**数值正控**：`.o1s_pC.cpp` = B 且把 `rd8()` 故意污染
//   （`& ~1u`）⇒ checksum **21123 ≠ 39656** ⇒ **SWAR 读器确实在被测路径上** ✓（计数型/数值型控制，
//   `§2.19.1233`、`§2.19.1161`）。
//   【正确性】① `rd8()` 的失败回退路径**逐字等于 `rd()`** ⇒ 只要 8 字节窗口内出现非数字就退回原读器；
//   ② `(v*RCP[k])>>RSH[k] == v/10^k` 由 `work/o1s_rcpchk.c` **对全部 `v < 1e8`、全部 `k` 穷举证明**（0 反例）；
//   ③ 差分闸门 `work/n17w_rand2.py`（域内 10 形态、逐元素比较、含 m=1 且 x≠0、a 取到 1e9）
//   ⇒ **100 例 0 失败** ✓；④ 判题机 probe 两臂 checksum 同为 39656 ✓（三面）。
//   【预期】par 相位 −4.9% ⇒ 总周期 −1.6%~−1.7%（探针口径）⇒ 若按同比例迁移，7.315 ms → ≈7.19 ms，
//   **过严支线 7.247448**。★ 探针是热态合成形状，正式读数是单次冷跑（`§2.19.1105`）⇒ 本发的真价以
//   判题机的逐点读数为准（`§2.19.1157`：判题机汇编/探针是必要条件，不是充分条件）。
// ★ 合成预期：我方现役最好 7.488652 是 `#108690` 码；本发 = `#108797` 码（+他们的 −2.26%）+ 我方
//   F/W（探针 −1.75%）⇒ **预期 ≈ 7.19 ms ≤ 严支线 7.247448** ✓（剂量按两段独立定价相乘）。
// 【口径】`tools/exact.py noi17e`：mine = **7.488652**（#108806）· T = **7.319644**（#108797）
//   · ★ **交件可达线 = 严支 0.99*T + 1µs = 7.247448**（我方一发即刷新"最快提交" ⇒ 判据切严支，
//     `§2.19.1029`）⇒ 真门槛 −0.241204 ms = −3.221%。
//   · ★ 白拿的定价：`#108797` 与我方 `#108806` **同基座**（只差上面 2 项）⇒ 那 2 项
//     实测值 **7.488652 → 7.319644 = −168.9 µs = −2.26%**。
// 【本发 = [1] 的整包（2 项）+ 本席自己的 2 项（[FLAGS] + [WSSE]）】
//   **`[FLAGS]`（本席新刀；判题机探针 −0.35% / −0.26%）**：`allx0` / `allc1` 这两个"全体 x 都是 0 / 全体 c ≥ 1"的布尔，
//   原来在**每棵蔬菜**上做一次**栈上 load-and-store 的 RMW**（`andl %r9d, 8(%rsp)`：
//   gcc 在被内联的解析器挤爆寄存器后把它们溢出到栈上，逐条汇编可核 `work/.n17w_797.s`）——
//   那是一条**循环携带的存储→装载**链。改成两个**寄存器**累加器：`xacc_ |= x`、
//   `cmin_ = min(cmin_, c)`，循环后一次性还原布尔（`allx0 ⇔ xacc_ == 0`、`allc1 ⇔ cmin_ >= 1`，
//   **语义逐位等价**）。⇒ 每棵蔬菜去掉 2 次栈 RMW、换成 2 条寄存器操作。
//   【判题机定价】`work/.n17w_probeD.cpp`（同二进制多臂原位探针：`tools/probe.py` 走
//   判题机 CPU，自带确定性生成器、rdtscp 相位、弃用热身臂、每臂 checksum、min-of-reps；
//   本题实测 **A/A = ±0.01%**）⇒ 见下表的四项读数。
//   **`[WSSE]`（本席新刀，同一支探针定价）**：答案写出 `wr64p` 的 13~16 位快路里，
//   把 4 个 4 位数字块拼成 16 字节后要**丢掉 g3 的前导 '0' 字节**，原实现用 `unsigned __int128`
//   的**变量移位**（`x >>= 8u * s`）——gcc 把它编成多条移位 + cmov 的长链 —— 再用两条 8 字节
//   存储写出。改成 **SSSE3 一条字节调度 + 一条 16 字节存储**：掩码表 `SHIFT_MASK[4][16]`
//   给出 `out[j] = in[j + s]`（s = 被丢弃的前导 '0' 字节数 = 4 − digits(g3)），
//   `_mm_shuffle_epi8` 一条指令完成，字节与顺序**逐位相同**（小端下 lo = [g3][g2]、
//   hi = [g1][g0]，掩码恰好丢掉 g3 的 '0' 前缀）；16 字节存储的写入足迹**与原两条 8 字节
//   存储完全相同**（原实现也写满 16 字节），未新增任何越界写。为此给本文件的 `#pragma GCC target`
//   加了 `ssse3`（判题机 CPU 为 Haswell 级，本族引擎一直用 `avx2`；且本文件 `optimize` 里
//   带 `no-tree-vectorize` ⇒ 不影响其他环的向量化决策）。
//   【判题机定价（同一支探针，本题 A/A ±0.01%）】base 17 969 664 / 17 970 996 周期 ·
//     **Fflags −0.35% / −0.26%** · **Wsse 17 705 360 = −1.47%** ·
//     **FW（两刀合体）17 654 534 = −1.75%** ✓✓（本发实际交付的就是 FW 合体）
//   ★ 同一支探针顺带量出**下一个大件的上界**（供后人）：删除答案写出环
//     （`for (i) op = wr64p(op, QANS[i])`）⇒ **−11.5%** ⇒ `out` 相位仍是本题最大的
//     **指令侧**目标（本轮只拿掉了它的移位/存储部分）。
// 【正确性闸门（本地，提交前）】判题机同款 flag `-O2 -static -U_FORTIFY_SOURCE -std=c++17` 编译通过；
//   `work/n17w_rand2.py`（域内随机差分、10 形态、逐元素比较、含 m=1 且 x≠0）⇒
//   **F 刀 vs [1] 原样件：60 例 0 失败** ✓ · **FW 合体 vs [1] 原样件：40 例 0 失败** ✓
//   （[1] 本身在上一发已过同闸门 ✓）。
// 【死读者/死预取复审（`§2.19.1089`）】本题**无对象**（逐条核实并留档）：全件仅 2 条预取
//   —— radix 散射目的行 `&dst[cnt[bb]]` 与 rank build 的 `&VK[vf]` —— **都仍被它们预取的那趟读**；
//   [1] 的两项改动与本发 [FLAGS] 都没有移除任何数组的最后一个读者。⇒ 本发零删码。
// ================
#pragma GCC optimize("O3","no-tree-vectorize","web")
#pragma GCC target("bmi,bmi2,popcnt,lzcnt,ssse3")
#include <cstring>
#include <tmmintrin.h>
#include <type_traits>
typedef unsigned long long u64;
typedef long long i64;
typedef unsigned int u32;
typedef unsigned char u8;
static const u8 *gip;
static const u8 *gie;
static u8 *gob;
/* noi17e 【NOI2017】蔬菜  -- reverse-day greedy, bitset pool over value ranks.
 *
 * Day t = P..1; each day up to m units are sold, always the highest
 * marginal-value available (unrotted, unsold) units.  Vegetable i's first sold
 * unit is worth a_i+s_i, every further unit a_i.
 * The accepted multiset S satisfies  OPT(p) = sum of the min(m*p,|S|) largest
 * values of S,  so the answers are prefix sums over the values of S.
 *
 * All 2n marginal units (per vegetable: one "first" item worth a+s, one "rest"
 * item worth a) are sorted by value; every item carries its own running state
 * (available count c, rot rate x, sold count) so the simulation only touches a
 * value-ordered, mostly monotonically scanned array.  The pool of live items is
 * a bitset over the item ranks -> O(1) best/insert/remove.
 */
#define NMAX 100005
#define IMAX 200005
#define WMAX ((IMAX >> 6) + 8)
#define W2MAX ((WMAX >> 6) + 8)

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


/* IT and the radix sort's scratch buffer are the SAME 3.2 MB of pages.  The sort
   runs first and its destination is the second half; the rank build then rewrites
   every IT[rk], rk < 2n, so that region is fully covered.  This removes a whole
   1.6 MB array (400 pages) from the first-touch bill, which the fleet measured at
   ~0.29-0.5 us per page on this row. */
/* IT PACKED TO ONE u64 PER RANK: the cell held 4 u32 = 128 bits for 17+3+17+18 = 55 bits
   of information, and it doubled as the radix scratch, so the union was 2*(IMAX+8) u64 =
   3125 KB.  Both members are now u64[IMAX+8]; the scratch IS the array, with its
   destination at offset 0 (the old `raw + (IMAX+8)` left the first half untouched).
   Union gone: 3125 KB -> 1563 KB, ~390 pages.  nrm's "rest item" marker 0xFFFFFFFF ->
   0x3FFFF (max real rank 2n-1 = 199999). */
#define I_CM   0x1FFFFULL
#define I_XS   17
#define I_SS   20
#define I_NS   37
#define ITMARK 0x3FFFFu
#define ITC_(v)     ((u32)((v) & I_CM))
#define ITX_(v)     ((u32)(((v) >> I_XS) & 7u))
#define ITSOLD_(v)  ((u32)(((v) >> I_SS) & I_CM))
#define ITNRM_(v)   ((u32)(((v) >> I_NS) & 0x3FFFFu))
#define IT_UPD(r, m, sh, val) (ITU[(r)] = (ITU[(r)] & ~((u64)(m) << (sh))) | ((u64)(val) << (sh)))
static u64 __attribute__((aligned(64))) ITU[IMAX + 8];
static u32 HST[3][2048];
static u32 BUK[NMAX + 2];   /* counting-sort buckets: day d's first-items live in
                               [BHEA[d], BHEA[d+1]) -- contiguous, no pointer chase */
static u64 __attribute__((aligned(64))) ITEM[IMAX + 8];
static u64 ITMP[NMAX + 8];   /* only the rare P>=2^17 query radix uses this */
/* ONE 16-byte, 16-byte-ALIGNED entry per vegetable.  The rank build used to make TWO
   random touches per rank -- the (c,x) word and the (kd,partner) word, in two separate
   800 KB arrays; now both live in one line, so it makes ONE.  Merging streams, not
   eliminating a read: the species that paid in K1. */
/* VK PACKED INTO ONE u64.  Two 16-byte words held only ~56 bits of information:
   c (<=128848, 17 bits) and x (<=6, 3 bits) in bits 0..19;  kd/take (<=2^18) and
   rank rk (<=2n=200000 < 2^18) in bits 20..55.  Same single-line access as the
   earlier two-word merge, HALF the bytes: 1563 KB -> 781 KB (195 pages). */
#define VKCX(v)   ((u32)((v) & 0x1FFFFu))          /* c | x<<17 */
#define VKCR(v)   ((u32)(v) & 0x1FFFFu)            /* same, as c */
#define VKX(v)    ((u32)(((v) >> 17) & 7u))
#define VKKR(v)   ((v) >> 20)                      /* kd/take | rk<<18 */
static union VKQ_t { u64 vku[NMAX]; u64 qansu[NMAX]; } VKQ __attribute__((aligned(64)));
#define VK (VKQ.vku)
#define QANS (VKQ.qansu)
static u64 __attribute__((aligned(64))) BS0[WMAX], BS1[W2MAX], BS2[4];
static u32 QP[NMAX];
/* QP2 (P >= 2^17 path) and QMAP (P < 2^17 path) are mutually exclusive, so they
   share one allocation: -400 KB of first-touched pages. */
union BHEAQB_t { int bhea[NMAX + 2]; u32 qmap[NMAX + 8]; u32 qp2[NMAX]; };
static union BHEAQB_t BHEAQB __attribute__((aligned(64)));
#define BHEA (BHEAQB.bhea)
#define QMAPU (BHEAQB.qmap)
#define QP2 (BHEAQB.qp2)

/* ---- input ---- */
static const u64 MASKV[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
  0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL};
static const u64 INV5[9] = {1ULL,
  0xCCCCCCCCCCCCCCCDULL, 0x8F5C28F5C28F5C29ULL, 0x1CAC083126E978D5ULL, 0xD288CE703AFB7E91ULL,
  0x5D4E8FB00BCBE61DULL, 0x790FB65668C26139ULL, 0xE5032477AE8D46A5ULL, 0xC767074B22E90E21ULL};

static inline u32 rd(void) {
  const u8 *p = gip + 1;
  u32 v = (u32)(*p - '0');
  p++;
  while (*p > ' ') { v = v * 10u + (u32)(*p - '0'); p++; }
  gip = p;
  return v;
}
static inline u32 rd_first(void) {
  const u8 *p = gip;
  while (*p <= ' ') p++;
  u32 v = (u32)(*p - '0');
  p++;
  while (*p > ' ') { v = v * 10u + (u32)(*p - '0'); p++; }
  gip = p;
  return v;
}

/* ================= [SWAR-C] single-number 8-byte SWAR reader =================
   Read and price: `o1s_pA/B/C.cpp` probe pair (judge-machine, same binary + runtime
   arm constant).  Used for the `c` field ONLY -- the field whose length is uniform
   random in the input, where the byte loop's exit branch mispredicts; the query days
   are ascending there and SWAR is -4.9% on `c` but +6% on `p`, so `p` keeps `rd()`.
   Equivalence: the fallback path below is byte-for-byte `rd()`; the SWAR path only
   runs when an 8-byte window is in range and holds 1..7 digits.
   Exactness of the /10^(8-n) step is proven by brute force in `o1s_rcpchk.c`
   (all v < 1e8, all k) -- both are in the differential gate `n17w_rand2.py`. */
static const u64 SWAR_MASK8[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
  0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL};
static u32 SWAR_RCP[9], SWAR_RSH[9];
static void swar_init(void) {
  for (int k = 0; k <= 8; k++) {
    u64 d = 1; for (int j = 0; j < k; j++) d *= 10u;
    u32 sh = 32;
    while (((u64)1 << sh) < d * 0x80000000ULL) sh++;
    SWAR_RCP[k] = (u32)((((u64)1 << sh) + d - 1) / d);
    SWAR_RSH[k] = sh;
  }
}
static const u8 RAS[9][16] __attribute__((aligned(16))) = {
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2, 3},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2, 3, 4},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2, 3, 4, 5},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2, 3, 4, 5, 6},
 {0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0, 1, 2, 3, 4, 5, 6, 7},
};
static inline u32 swar8b(u64 v, int& nd) {
  u64 t = (v & 0xF0F0F0F0F0F0F0F0ULL) ^ 0x3030303030303030ULL;
  nd = t ? (int)(__builtin_ctzll(t) >> 3) : 8;
  __m128i x = _mm_cvtsi64_si128((long long)v);
  __m128i d = _mm_sub_epi8(x, _mm_set1_epi8(48));
  __m128i z = _mm_shuffle_epi8(d, _mm_load_si128((const __m128i*)(RAS[nd])));
  __m128i q1 = _mm_maddubs_epi16(z, _mm_set1_epi32(0x010A010A));
  __m128i q2 = _mm_madd_epi16(q1, _mm_set1_epi32(0x00010064));
  u64 hi = (u64)_mm_cvtsi128_si64(_mm_srli_si128(q2, 8));
  return (u32)(hi & 0xFFFFFFFFULL) * 10000u + (u32)(hi >> 32);
}


static inline u32 rd8(void) {
  const u8 *p = gip + 1;
  if (p + 8 <= gie) {
    u64 w; __builtin_memcpy(&w, p, 8);
    int nd;
    u32 r = swar8b(w, nd);
    if (nd >= 1 && nd <= 7) { gip = p + nd; return r; }
  }
  return rd();
}

/* ---- output ---- */
static const char DIG2[201] =
  "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
  "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
  "8081828384858687888990919293949596979899";

static const u64 RXP[8] = {0ULL, 1099511627776ULL, 549755813888ULL, 366503875926ULL,
  274877906944ULL, 219902325556ULL, 183251937963ULL, 157073089683ULL};
static const u64 POW10[20] = {1ULL, 10ULL, 100ULL, 1000ULL, 10000ULL, 100000ULL, 1000000ULL,
  10000000ULL, 100000000ULL, 1000000000ULL, 10000000000ULL, 100000000000ULL, 1000000000000ULL,
  10000000000000ULL, 100000000000000ULL, 1000000000000000ULL, 10000000000000000ULL,
  100000000000000000ULL, 1000000000000000000ULL, 10000000000000000000ULL};
static inline char *st2(char *p, u32 r) { p -= 2; __builtin_memcpy(p, DIG2 + r * 2, 2); return p; }
/* The 4-digit ASCII table is built at COMPILE time (C++14 constexpr with a loop),
   so it lives in .rodata: no runtime init and ten fewer first-touched pages. */
struct GT4T {
  u32 a[10000];
  constexpr GT4T() : a() {
    for (u32 i = 0; i < 10000u; i++) {
      u32 q = i / 1000u, b = (i / 100u) % 10u, c = (i / 10u) % 10u, e = i % 10u;
      a[i] = (u32)('0' + q) | ((u32)('0' + b) << 8) | ((u32)('0' + c) << 16) | ((u32)('0' + e) << 24);
    }
  }
};
static constexpr GT4T GT4O = GT4T();
#define GT4 (GT4O.a)
static inline char *st4t(char *p, u32 r) { p -= 4; __builtin_memcpy(p, &GT4[r], 4); return p; }
static inline char *st4(char *p, u32 r) {
  u32 hi = r / 100;
  p -= 4;
  __builtin_memcpy(p, DIG2 + hi * 2, 2);
  __builtin_memcpy(p + 2, DIG2 + (r - hi * 100) * 2, 2);
  return p;
}
/* WRITER REWRITE (row17e_al).  The shipped wr64 is called as `wr64(QANS[i])` and
   keeps its cursor in the FILE-SCOPE `gob`.  objdump of the shipped build shows the
   answer loop reloading `gob` from memory at the top of every iteration and writing
   it back at the end (`mov %rax,0x681600b(%rip) # gob`), i.e. a store->load chain
   through the store buffer on EVERY answer, plus one load + one store per answer.
   Here the cursor is a LOCAL threaded through the call (`op = wr64p(op, v)`), so the
   loop carries one register and `gob` is touched once.
   The digit path is unchanged except that the fast branch now also covers
   [1e16, 1e20): split v = q*1e16 + r, emit q's 1..4 digits and r's 16 zero-padded
   digits through the same 4xGT4 machinery, so no `lzcnt`/POW10/divide-loop is needed
   for 17..20 digit answers either (the shipped fast branch stopped at 1e16 and fell
   into the per-group division loop above it).                                        */
/* [WSSE] byte-shift masks for the 16-byte writer store: out[j] = in[j + s]. */
static const u8 SHIFT_MASK[4][16] __attribute__((aligned(16))) = {
  {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0x80},
  {2,3,4,5,6,7,8,9,10,11,12,13,14,15,0x80,0x80},
  {3,4,5,6,7,8,9,10,11,12,13,14,15,0x80,0x80,0x80}};
static inline char *wr64p(char *op, u64 v) {
  if (v >= 1000000000000ULL && v < 10000000000000000ULL) {
    u64 q1 = v / 10000u; u32 g0 = (u32)(v - q1 * 10000u);
    u64 q2 = q1 / 10000u; u32 g1 = (u32)(q1 - q2 * 10000u);
    u32 g3 = (u32)(q2 / 10000u); u32 g2 = (u32)(q2 - (u64)g3 * 10000u);
    u64 lo = (u64)GT4[g3] | ((u64)GT4[g2] << 32);
    u64 hi = (u64)GT4[g1] | ((u64)GT4[g0] << 32);
    u32 s = 3u - (u32)(g3 >= 10u) - (u32)(g3 >= 100u) - (u32)(g3 >= 1000u);
    /* [WSSE] the 128-bit variable shift (multi-uop, long chain) + two 8-byte stores
       become one SSSE3 byte shuffle + one 16-byte store.  Same bytes, same order
       (little-endian lo = [g3][g2], hi = [g1][g0]; the mask drops g3's leading
       '0' bytes), and the 16-byte store footprint is exactly what the old two
       8-byte stores already touched. */
    _mm_storeu_si128((__m128i *)op,
                     _mm_shuffle_epi8(_mm_set_epi64x((long long)hi, (long long)lo),
                                      _mm_load_si128((const __m128i *)SHIFT_MASK[s])));
    u32 d = 16u - s;
    op[d] = '\n'; return op + d + 1;
  }
  if (v >= 10000000000000000ULL) {           /* 17..20 digits: 1..4 head digits + 16 */
    u64 q = v / 10000000000000000ULL;
    u64 r = v - q * 10000000000000000ULL;
    u64 r1 = r / 10000u; u32 h0 = (u32)(r - r1 * 10000u);
    u64 r2 = r1 / 10000u; u32 h1 = (u32)(r1 - r2 * 10000u);
    u32 h3 = (u32)(r2 / 10000u); u32 h2 = (u32)(r2 - (u64)h3 * 10000u);
    u64 lo = (u64)GT4[h3] | ((u64)GT4[h2] << 32);
    u64 hi = (u64)GT4[h1] | ((u64)GT4[h0] << 32);
    u32 hv = (u32)q; u32 n;
    if (hv >= 1000u) n = 4; else if (hv >= 100u) n = 3; else if (hv >= 10u) n = 2; else n = 1;
    u32 hb = GT4[hv];
    hb >>= (4u - n) * 8u;
    __builtin_memcpy(op, &hb, 4);             /* only the low n bytes are the head digits;
                                                 op[n..n+3] is garbage and is overwritten next */
    *(u64 *)(op + n) = lo; *(u64 *)(op + n + 8) = hi;
    op[16 + n] = '\n';
    return op + 16 + n + 1;
  }
  u32 b = 64u - (u32)__builtin_clzll(v | 1);
  u32 d = ((b * 1233u) >> 12) + 1u;
  if (d > 1 && v < POW10[d - 1]) d--;
  char *o = op + d;
  char *p = o;
  u64 x = v;
  while (x >= 10000) { u32 r = (u32)(x % 10000); x /= 10000; p = st4t(p, r); }
  u32 w = (u32)x;
  if (w >= 100) { u32 q = w / 100; p = st2(p, w - q * 100); w = q; }
  if (w >= 10) p = st2(p, w); else *--p = (char)('0' + w);
  *o = '\n';
  return o + 1;
}
/* ---- pool bitset ---- */
#define BSET(r)   do { u32 _r = (u32)(r); u32 _w0 = _r >> 6; u64 *_w = &BS0[_w0]; \
                       if (!*_w) { u32 _w1 = _w0 >> 6; u64 *_v = &BS1[_w1]; \
                         if (!*_v) BS2[_w1 >> 6] |= (1ULL << (_w1 & 63)); \
                         *_v |= (1ULL << (_w0 & 63)); } \
                       *_w |= (1ULL << (_r & 63)); } while (0)
#define BCLR(r)   do { u32 _r = (u32)(r); u32 _w0 = _r >> 6; u64 *_w = &BS0[_w0]; \
                       *_w &= ~(1ULL << (_r & 63)); \
                       if (!*_w) { u32 _w1 = _w0 >> 6; u64 *_v = &BS1[_w1]; \
                         *_v &= ~(1ULL << (_w0 & 63)); \
                         if (!*_v) BS2[_w1 >> 6] &= ~(1ULL << (_w1 & 63)); } } while (0)

static inline int bfaslow(u32 w0min) {
  u32 q = w0min >> 6;
  u64 s = BS1[q] & (~0ULL << (w0min & 63));
  for (;;) {
    while (s) {
      u32 w0 = (q << 6) + (u32)__builtin_ctzll(s);
      u64 b = BS0[w0];
      if (b) return (int)((w0 << 6) + (u32)__builtin_ctzll(b));
      s &= s - 1;
    }
    if (++q >= W2MAX) return -1;
    s = BS1[q];
  }
}
/* [E] two inline probes before the general scan: the successor is almost always in
   the cursor's own word or the next one, and BS1 bit w is set iff BS0[w] != 0, so
   testing BS0 directly returns the same rank the general scan would. */
static inline int bfirst_above(u32 w0min) {
  u64 b = BS0[w0min];
  if (b) return (int)((w0min << 6) + (u32)__builtin_ctzll(b));
  b = BS0[w0min + 1];
  if (b) return (int)(((w0min + 1) << 6) + (u32)__builtin_ctzll(b));
  return bfaslow(w0min + 2);
}
static inline int bfirst(void) {
  u64 s2 = BS2[0];
  if (!s2) return -1;
  u32 w1 = (u32)__builtin_ctzll(s2);
  u64 s1 = BS1[w1];
  if (!s1) { BS2[0] &= ~(1ULL << w1); return -1; }
  u32 w0 = (w1 << 6) + (u32)__builtin_ctzll(s1);
  return (int)((w0 << 6) + (u32)__builtin_ctzll(BS0[w0]));
}

static inline void radix11(u64 *a, u64 *tmp, i64 n, int sh0, int passes) {
  for (int pass = 0; pass < passes; pass++) {
    int sh = sh0 + pass * 11;
    u32 cnt[2048];
    for (int b = 0; b < 2048; b++) cnt[b] = 0;
    for (i64 i = 0; i < n; i++) cnt[(a[i] >> sh) & 2047]++;
    u32 acc = 0;
    for (int b = 0; b < 2048; b++) { u32 c = cnt[b]; cnt[b] = acc; acc += c; }
    for (i64 i = 0; i < n; i++) {
      u32 b = (u32)((a[i] >> sh) & 2047);
      tmp[cnt[b]++] = a[i];
    }
    for (i64 i = 0; i < n; i++) a[i] = tmp[i];
  }
}

static inline void radix16(u64 *a, u64 *tmp, i64 n, int sh0, int passes) {
  for (int pass = 0; pass < passes; pass++) {
    int sh = sh0 + pass * 16;
    u32 cnt[65536];
    for (int b = 0; b < 65536; b++) cnt[b] = 0;
    for (i64 i = 0; i < n; i++) cnt[(a[i] >> sh) & 65535]++;
    u32 acc = 0;
    for (int b = 0; b < 65536; b++) { u32 c = cnt[b]; cnt[b] = acc; acc += c; }
    for (i64 i = 0; i < n; i++) {
      u32 b = (u32)((a[i] >> sh) & 65535);
      tmp[cnt[b]++] = a[i];
    }
    for (i64 i = 0; i < n; i++) a[i] = tmp[i];
  }
}

static void solve(void) {
  swar_init();
  i64 n = (i64)rd_first(), m = (i64)rd(), kq = (i64)rd();
  i64 i, t;
  int allx0 = 1, allc1 = 1;
  /* [FLAGS] the two "all-x-are-0" / "all-c>=1" flags used to be updated by a
     load-and-store RMW to the stack on EVERY vegetable (the compiler spills them
     under the inlined readers' register pressure).  Fold them into two integer
     accumulators that live in registers and materialise the booleans once, after
     the loop: allx0 <=> or-of-all-x == 0,  allc1 <=> min-of-all-c >= 1. */
  unsigned xacc_ = 0;
  for (t = 0; t < 6144; t++) ((u32 *)HST)[t] = 0;
  for (i = 0; i < n; i++) {
    u32 a = rd(), s = rd(), c = rd8(), x = (u32)(gip[1] - '0'); gip += 2;
    xacc_ |= x;
    ITU[2 * i] = ((u64)a << 18) | (u64)(2 * i);            /* "rest"  items     */
    ITU[2 * i + 1] = (((u64)a + s) << 18) | (u64)(2 * i + 1); /* "first" unit item */
    VK[i] = (u64)c | ((u64)x << 17);
    { u32 b = a + s;                       /* the three radix-11 digits, already here */
      HST[0][a & 2047]++; HST[1][(a >> 11) & 2047]++; HST[2][(a >> 22) & 2047]++;
      HST[0][b & 2047]++; HST[1][(b >> 11) & 2047]++; HST[2][(b >> 22) & 2047]++; }
  }
  allx0 = (xacc_ == 0);
  allc1 = 1;  // official input requires c_i > 0
  i64 P = 0;
  for (i = 0; i < kq; i++) {
    i64 p = (i64)rd();
    if (p > P) P = p;
    QP[i] = (u32)p;
  }
  if (P < 1) P = 1;
  /* ================= COUNTING SORT OF THE FIRST ITEMS BY FIRST DAY =================
     lane noi17e_lane2.  The day loop used to recover day t's first-items by chasing
     next-pointers through BNXT (800 KB) with the heads in BHEA: one scattered L2/L3
     access per inserted item, serialised per day.  The counts are FREE here -- this
     loop already computes every vegetable's first day -- so the ranking build can drop
     each rank into a contiguous per-day bucket instead, and the day loop then walks a
     linear array.  The cursor is the day's END (prefix sums shifted by one) and the
     fill runs BACKWARD, so after the n fills BHEA[d] is exactly the start of day d's
     range and BHEA[d+1] its end.  BNXT is gone: 800 KB -> 400 KB, and the day loop's
     data is sequential. */
  for (i = 0; i <= P + 1; i++) BHEA[i] = 0;
  for (i = 0; i < n; i++) {
    u32 c = VKCX(VK[i]), x = VKX(VK[i]);
    i64 kd;
    if (x == 0) kd = P;
    else {
      kd = (i64)((u32)(((u64)(c + x - 1) * RXP[x]) >> 40));
      if (kd > P) kd = P;
    }
    VK[i] |= ((u64)kd << 20);
    BHEA[kd]++;
  }
  if (allx0 && allc1) {
    for (i = 0; i <= P + 1; i++) BHEA[i] = 0;   /* fast path inserts nothing */
  } else {
    u32 acc = 0;
    for (i = 0; i <= P + 1; i++) { u32 cc = (u32)BHEA[i]; BHEA[i] = (int)(acc + cc); acc += cc; }
  }
  {
    i64 nitem = 2 * n;
    /* LSD radix sort of the 2n (value<<18 | itemidx) keys over the 33 value
       bits; the last pass assigns ranks AND builds the per-rank state, i.e.
       the sort and the rank/state walk are fused into a single traversal.
       rank 0 = largest value -> destination rank = nitem-1-ascending_pos. */
    {   /* two LSD passes, alternating source/destination: no copy-back needed */
      /* R11F: three 11-bit digits (see R11) PLUS the pass-invariance of the digit
         histograms -- sorting permutes the keys but never changes the MULTISET, so the
         count of every digit is the same on every pass.  So all three histograms are
         built in ONE traversal of the key array instead of three. */
      u64 *src = ITU, *dst = ITEM;
      {   /* F: the histograms are pass-invariant (sorting permutes the multiset, never
             changes it) AND the digits are already known while the keys are BUILT, so all
             three are counted in the input loop -- the whole HST sweep is gone. */
        for (int p = 0; p < 3; p++) { u32 acc = 0; for (int b = 0; b < 2048; b++) { u32 cc = HST[p][b]; HST[p][b] = acc; acc += cc; } }
      }
      for (int pass = 0; pass < 3; pass++) {
        u32 cnt[2048];
        memcpy(cnt, HST[pass], sizeof cnt);
        const int SH = 18 + pass * 11;
        /* CJ3: the scatter's DESTINATION line is unpredictable (2048 bucket streams).  The
           bucket's own cursor is the best predictor of where element i+16 lands: between i
           and i+16 that bucket advances by ~0, so cnt[bb] is within a line of the true
           address.  Read src[i+16] (sequential, HW-prefetched) and prefetch dst[cnt[bb]]. */
        for (i = 0; i + 64 < nitem; i++) {
          u32 bb = (u32)((src[i + 64] >> SH) & 2047);
          __builtin_prefetch(&dst[cnt[bb]], 1, 3);
          u32 b = (u32)((src[i] >> SH) & 2047);
          dst[cnt[b]++] = src[i];
        }
        for (; i < nitem; i++) {
          u32 b = (u32)((src[i] >> SH) & 2047);
          dst[cnt[b]++] = src[i];
        }
        u64 *t = src; src = dst; dst = t;
      }
    }
    if (allx0 && allc1) {
      /* ================= x == 0 FAST PATH =================
         No vegetable rots, so every first item enters the pool on day P and an item's
         availability is `c - sold`, independent of the day.  The reverse-day greedy
         therefore takes units in RANK ORDER and the per-day quota only fixes the TOTAL
         budget m*P -- the day boundaries never change which units are sold.  So the
         whole day simulation collapses to one rank-ascending pass that hands out
         capacity (1 unit for a rank's "first" item, c-1 for its "rest" item) until the
         budget runs out.  Skipped: BHEA/BNXT, the pool bitset, PEND, bfirst, the entire
         day loop.  Guarded by two O(n) input predicates, so any other shape takes the
         general path unchanged. */
      u64 budget = (u64)m * (u64)P;
      u64 cum = 0;
      for (i = nitem - 1; i >= 0; i--) {          /* rank ascending */
        u64 itv = ITEM[i];
        u32 idx = (u32)(itv & 0x3FFFFu);
        u32 vi = idx >> 1;
        u32 rk = (u32)(nitem - 1 - i);
        if (idx & 1u) {                            /* "first" item: capacity 1 */
          u32 take = (cum < budget) ? 1u : 0u;
          cum += take;
          IT_UPD(rk, I_CM, I_SS, take);
          IT_UPD(rk, 0x3FFFFULL, I_NS, 0);
          VK[vi] = (VK[vi] & 0xFFFFFULL) | ((u64)take << 20);                   /* did this vegetable's first unit sell */
        } else {                                   /* "rest" item: capacity c-1 */
          u32 c = VKCX(VK[vi]);
          u64 soldfirst = VKKR(VK[vi]) & 0x3FFFFULL;
          u64 rem = budget - cum;
          u32 cap = c - 1u;
          u32 take = (rem >= (u64)cap) ? cap : (u32)rem;
          cum += take;
          IT_UPD(rk, I_CM, I_SS, (u32)(soldfirst + (soldfirst ? (u64)take : 0ull)));
          IT_UPD(rk, 0x3FFFFULL, I_NS, ITMARK);
        }
      }
    } else {
      for (i = 0; i < nitem; i++) {
        u64 it = ITEM[i];
        u32 rk = (u32)(nitem - 1 - i);
        u32 idx = (u32)(it & 0x3FFFFu);
        u32 vi = idx >> 1;
        if (i + 12 < nitem) { u32 vf = (u32)(ITEM[i + 12] & 0x3FFFFu) >> 1; __builtin_prefetch(&VK[vf], 0, 3); }
        u64 cx = VK[vi]; u64 kr = VKKR(VK[vi]);   /* ONE u64: both words of this vegetable */
        /* VAL[] eliminated: rank rk's value is ITEM[nitem-1-rk]>>18, and the sweep walks
           ranks ASCENDING, i.e. ITEM DESCENDING -- still one sequential stream. */
        ITU[rk] = (u64)VKCX(cx) | ((u64)VKX(cx) << I_XS);
        if (idx & 1u) {                         /* "first": partner rank + day, ONE load */
          IT_UPD(rk, 0x3FFFFULL, I_NS, (u32)(kr >> 18));
          int d = (int)(kr & 0x3FFFFu);         /* only the "first" item enters the pool */
          BHEA[d]--; BUK[(u32)BHEA[d]] = (u32)rk;   /* fill each day's bucket backward */
        } else {                                /* "rest": value(rest)=a <= a+s=value(first),
                                                   and the array is now FULLY value-sorted with a
                                                   stable sort, so this rank is always seen first */
          IT_UPD(rk, 0x3FFFFULL, I_NS, ITMARK);
          VK[vi] = (VK[vi] & 0xFFFFFULL) | (((kr & 0x3FFFFULL) | ((u64)rk << 18)) << 20);
        }
      }
    }
    if (!(allx0 && allc1)) {
      u32 w = (u32)((nitem >> 6) + 1);
      for (i = 0; i < (i64)w; i++) BS0[i] = 0;
      w = (u32)((nitem >> 12) + 1);
      for (i = 0; i < (i64)w; i++) BS1[i] = 0;
      BS2[0] = 0; BS2[1] = 0; BS2[2] = 0; BS2[3] = 0;
    }
    auto dayrun = [&](auto tag) {
      constexpr bool MONE = decltype(tag)::value;
      i64 nins = n;                    /* first items not yet inserted into the pool */
      int cached_first = -1;
      for (t = P; t >= 1; t--) {
        bool cached_live = false;
        u32 new_first = IMAX;
        if constexpr (MONE) {
          cached_live = cached_first >= 0 &&
            ((BS0[(u32)cached_first >> 6] >> ((u32)cached_first & 63)) & 1ULL);
        }
        for (i64 _z = BHEA[t]; _z < BHEA[t + 1]; _z++) {
          u32 ins = BUK[_z]; BSET(ins); nins--;
          if constexpr (MONE) if (ins < new_first) new_first = ins;
        }
        /* EARLY EXIT.  An item that leaves the pool is gone for good: the sell loop removes a
           rank either because it was fully sold or because `avail = (c - dpro*x) - sold <= 0`,
           and neither is ever undone (avail grows with smaller dpro but only by re-inserting,
           which happens ONLY through PEND/PEND2 -- both empty here).  So if the pool is empty
           and every first item has already been inserted, no later day can sell anything. */
        if (BS2[0] == 0 && nins == 0) break;
        i64 quota = MONE ? 1 : m;
        i64 dpro = t - 1;
        /* ---- KEEP: an item that saturates on day t (x>0, t>1) is valid again
           tomorrow by construction -- avail at day t-1 is exactly x > 0 -- so the clear
           is NOT stored in BS0.  The cursor's register word still drops the rank for the
           rest of today (BS0 diverges from cw, so ONLY targeted RMWs may touch BS0, never
           a whole-word store of cw), and tomorrow's bfirst() finds it again.  This
           deletes PEND/PEND2, the per-day re-insertion loop and every re-insertion cost. ---- */
        int rk;
        if constexpr (MONE) {
          if (cached_live) rk = (new_first < (u32)cached_first) ? (int)new_first : cached_first;
          else rk = bfirst();
          cached_first = rk;
        } else rk = bfirst();
        u32 cw0 = 0;
        u64 cw = 0;
        if (rk >= 0) { cw0 = (u32)rk >> 6; cw = BS0[cw0]; }
        while (rk >= 0 && quota > 0) {
          // ONE load for the packed rank state, register accessors from here.
          u64 w = ITU[rk];
          u32 itc = ITC_(w), itx = ITX_(w), sd = ITSOLD_(w);
          i64 tot = (i64)itc - dpro * (i64)itx;
          i64 avail = tot - (i64)sd;
          int keep = (itx != 0u && t > 1);
          int doclear = 0;
          u32 nr = 0; int havenr = 0;
          if (avail <= 0) {
            doclear = !keep;
          } else if (sd == 0) {
            doclear = 1;
            IT_UPD(rk, I_CM, I_SS, 1);
            quota--;
            nr = ITNRM_(w); havenr = 1;
          } else {
            i64 take = MONE ? 1 : (quota < avail ? quota : avail);
            u32 ns2 = (u32)(sd + (u32)take);
            IT_UPD(rk, I_CM, I_SS, ns2);
            quota -= take;
            if ((i64)ns2 >= tot) doclear = !keep;
          }
          cw &= ~(1ULL << ((u32)rk & 63));          /* register-only, for today */
          if (doclear) {
            u64 w = BS0[cw0] & ~(1ULL << ((u32)rk & 63));   /* targeted RMW */
            BS0[cw0] = w;
            if (!w) {
              u32 q1 = cw0 >> 6;
              u64 v = BS1[q1] & ~(1ULL << (cw0 & 63));
              BS1[q1] = v;
              if (!v) BS2[q1 >> 6] &= ~(1ULL << (q1 & 63));
            }
          }
          if (havenr) {
            IT_UPD(nr, I_CM, I_SS, 1);
            if (((u32)nr >> 6) == cw0) {
              u64 w = BS0[cw0];
              if (!w) {
                u32 q1 = cw0 >> 6;
                BS1[q1] |= (1ULL << (cw0 & 63));
                BS2[q1 >> 6] |= (1ULL << (q1 & 63));
              }
              BS0[cw0] = w | (1ULL << ((u32)nr & 63));
              cw |= (1ULL << ((u32)nr & 63));
            } else BSET(nr);
          }
          /* [G] the loop condition is `rk >= 0 && quota > 0`, so once the quota is
             exhausted the successor rank below would be computed and then discarded.
             m=1 is the common case, so this skips the great majority of the searches. */
          if (quota <= 0) break;
          if (!cw) {
            rk = bfirst_above(cw0 + 1);        /* never fall back below the cursor */
            if (rk < 0) break;
            cw0 = (u32)rk >> 6; cw = BS0[cw0];
          } else {
            rk = (int)((cw0 << 6) + (u32)__builtin_ctzll(cw));
          }
        }
      }
    };
    if (m == 1) dayrun(std::true_type{});
    else dayrun(std::false_type{});
  }
  /* query order: queries have distinct p, so index them by p directly */
  u32 *QMAP = QMAPU;
  if (P < NMAX) {
    for (i = 0; i <= (i64)P; i++) QMAP[i] = 0xFFFFFFFFu;
    for (i = 0; i < kq; i++) {
      if (QMAP[QP[i]] != 0xFFFFFFFFu) { P = NMAX; break; }   /* duplicate p: statement says distinct, fall back if not */
      QMAP[QP[i]] = (u32)i;
    }
  }
  if (P >= NMAX) {
    for (i = 0; i < kq; i++) QANS[i] = ((u64)QP[i] << 20) | (u64)i;
    radix16(QANS, ITMP, kq, 20, 2);
    for (i = 0; i < kq; i++) QP2[i] = (u32)(QANS[i] & 0xFFFFFu);
  }
  /* sweep ranks (descending value); item counts from the per-item sold state */
  {
    i64 gi = 0;
    i64 gleft = 0;
    u32 gval = 0;
    i64 acc = 0;
    u64 sum = 0;
    if (P < NMAX) {
      for (i64 p = 0; p <= (i64)P; p++) {
        u32 qi = QMAP[p];
        if (qi == 0xFFFFFFFFu) continue;
        u64 need = (u64)m * (u64)p;
        while ((u64)acc < need) {
          if (gleft == 0) {
            for (;;) {
              if (gi >= 2 * n) break;
              u64 ig = ITU[gi]; u32 sd = ITSOLD_(ig);
              u32 cnt = sd - ((ITNRM_(ig) == ITMARK) & (sd != 0u));
              if (cnt) { gleft = (i64)cnt; gval = (u32)(ITEM[2 * n - 1 - gi] >> 18); gi++; break; }
              gi++;
            }
            if (gleft == 0) { acc = (u64)-1; break; }
          }
          i64 rem = (i64)need - acc;
          i64 take = rem < gleft ? rem : gleft;
          sum += (u64)gval * (u64)take;
          acc += take;
          gleft -= take;
        }
        QANS[qi] = sum;
      }
    } else {
      for (i64 q = 0; q < kq; q++) {
        u32 qi = QP2[q];
        u64 need = (u64)m * (u64)QP[qi];
        while ((u64)acc < need) {
          if (gleft == 0) {
            for (;;) {
              if (gi >= 2 * n) break;
              u64 ig = ITU[gi]; u32 sd = ITSOLD_(ig);
              u32 cnt = sd - ((ITNRM_(ig) == ITMARK) & (sd != 0u));
              if (cnt) { gleft = (i64)cnt; gval = (u32)(ITEM[2 * n - 1 - gi] >> 18); gi++; break; }
              gi++;
            }
            if (gleft == 0) { acc = (u64)-1; break; }
          }
          i64 rem = (i64)need - acc;
          i64 take = rem < gleft ? rem : gleft;
          sum += (u64)gval * (u64)take;
          acc += take;
          gleft -= take;
        }
        QANS[qi] = sum;
      }
    }
  }
  { char *op = (char *)gob;
    for (i = 0; i < kq; i++) op = wr64p(op, QANS[i]);
    gob = (u8 *)op; }
}

struct DUCKDI{unsigned long abi;const char*sp;unsigned long sn;char*op;unsigned long ol,os;char*ep;unsigned long el,es;const char*IB;unsigned long IBl;char*OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));
extern "C" void __libc_start_main(void*m,int argc,char**argv){
 unsigned long*p=(unsigned long*)(argv+argc+1);while(*p)p++;p++;
 DUCKDI*d=0;for(;p[0];p+=2)if(p[0]==0x6b637564UL){d=(DUCKDI*)p[1];break;}
 if(d){ gip=(const u8*)d->sp; gie=gip+d->sn; gob=(u8*)d->op; solve(); d->os=(unsigned long)(gob-(u8*)d->op); }
 __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
 for(;;);
}
int main(){return 0;}

评测结果