代码

// ===== REFERENCES (r9c2k_ 席 · 2026-10-15) =====
// [A] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#127420**
//     <https://duck.ac/submission/127420>（183.234520 ms = 本题现役最快件）。
//     用途：**本发正文 = 该件的逐字节副本**，只改【思路】所述一处表达式（两个站点），其余一字不动。
// [B] duck.ac 本账号公开提交 **#126876 / #126888**（`mmmc1k`，6.668521 / 6.658138 ms）与
//     **#127093**（`mmmc2k`，48.071916 ms）—— 「gray12」索引抽取收缩刀的**在役先例**：
//     把 `(w >> s) & M` 的**破坏性移位抽取**改写成**旋转** `(w>>s)|(w<<(W-s))`，在
//     `target("avx2,bmi2")` 下由 gcc9 编成三操作数 `rorx $imm,src,dst`（源不破坏），再把 `<<q`
//     折进掩码、表基址改 `char*` 预置字节偏移 ⇒ **每站点省掉那条 `mov` 副本**。
// [C] 队内器械/账（只读引用）：`.cache/knife_catalog.md` §C（gray12 行：三前提 + 两段判据 +
//     「热环内 >~10 处才够本」校准）· `problems/mmmc2k/work/r2m__tmp/r2m_gray12_card.md`（r2m_ 席完整一页卡）·
//     `.cache/live_loop_audit_card.md` · `.cache/index_family_scan_card.md`（r9c2k_ 席，本单所用三道闸与判族器）。
// LICENSE：以上均为 duck.ac 同站公开提交（站方 FAQ：你的代码将会被公开）与队内产物，
//     均无独立许可证声明 ⇒ 无可违反的条款；按竞赛站公开代码惯例具名引用原账号、提交号与用途。
// ======================
// ===== 思路（r9c2k_ 席 · 2026-10-15 · 单变量：基数排序直方图环的两处 10 位数字抽取）=====
// 【刀】`kruskal_sort()` 直方图环（源码 506 行）两处抽取（`HST3` 是 `u32[3][1024]` ⇒ 索引 scale 4）：
//   `HST3[1][(k >> RBITS) & RMASK]++` · `HST3[2][(k >> (2*RBITS)) & RMASK]++`
//   **恒等改写**：`((k>>10)&1023)*4 == (k>>8)&0xffc` · `((k>>20)&1023)*4 == (k>>18)&0xffc`
//   （右移 8/18 后 bit[2..11] 恰来自原 bit[10..19]/[20..29]，`0xffc` 正是这 10 位，回绕项落在 i<2 被掩掉）
//   ⇒ 写成 `HST3[p][ROR32(k, s) & RMASK]++`（**索引类型/掩码/寻址 scale 全部不动**）。
//   ★ 为什么**不**改 `char*` 基址（本席第一版，已被码流审计否掉）：本表元素是 u32 ⇒ 索引的
//     `scale 4` 是**硬件原生寻址尺度**，写成字节偏移反而逼 gcc 物化基址并插两条 `addq $4096`
//     ⇒ 环体 18→20（**+2**）；`char*`+字节偏移只在"表元素步长不是 1/2/4/8"时才必要。
// 【机理】原件在判题同款 gcc 9.3 下把 `(k>>s)&1023` 编成 `movl %eax,%ecx ; shrl $s,%ecx ; andl $1023,%ecx`
//   （破坏性移位必须先复制 k，因为 k 还要给下一处用）；旋转式给出三操作数 `rorx` ⇒ 每站点 3 条 → 2 条。
//   ★实测（本地探针 + 真件汇编复核）：原件两站点**共用同一条** `movl %eax,%ecx`
//   ⇒ **环体实际省 1 条/迭代**（不是 2 条）—— 本条已按实况上报协调者。
// 【闸门】`n18d_big0.in`（52 MB，T=3）判题形状**逐字节**对拍 + 官方形状 checksum + md5 + 阳性对照（0xffc→0xff8）。
// ======================
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#127065**
//     <https://duck.ac/submission/127065>（185.682468 ms = 本账号本题现最好件）。
//     用途：**本发正文 = 该件的逐字节副本**，只做下方【思路】所述的一处回退，其余一字不动。
// [2] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#126812**
//     <https://duck.ac/submission/126812>（185.030469 ms = 本题当前 T）。用途：**采用其在 KRT
//     并查集归并环上的"祖父级（第二跳）提示"形态** —— `h2u = dsu[pu]; h2v = dsu[pv];` 两次
//     真需求载入后 `prefetchw dsu[h2u]/dsu[h2v]`。该形态是 [2] 与我方在役件的三处差异之一，
//     且 [2] 自述 #126812 = 我方 #126790(192.640) + 三刀 = −7.610 ms。
// [3] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#126993** = 本发**回退**的那处
//     （`[r1noiQ3-DELGP]`）的原件：该刀**删掉**本形态，其原件注释逐字给出了删除理由
//     （两条随机真需求载入、perf 占全程序 2.13% 采样，结果只喂提示）；本发即把该处**单变量
//     回退**并上板定价（原件注释已随下方正文保留，便于对照）。
// [4] 本件下方原样保留了 #127065 继承的全部引用块与思路段。
// 【许可合规】以上均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处；
//     各件均未声明独立许可证（无许可证声明 ⇒ 无可违反的条款）✓
// ======================
// ===== 思路 =====
// 【性质】**单变量回退/定价发**：底盘 = 本账号 #127065 逐字节副本，正文只改**一处** ——
//   KRT（Kruskal 重构树）归并环里恢复**祖父级提示**：在第一级 `prefetchw dsu[pu]/dsu[pv]`
//   之后，加 `u32 h2u = dsu[pu], h2v = dsu[pv];` 两条真需求载入，并据其发
//   `prefetchw dsu[h2u]/dsu[h2v]`。其余（`span8`、`[C1c]`、`beg[]` 自任游标形态）一字不动。
// 【为什么值得发】(1) 该处**从未单变量定价**：它此前只以 `#126870 → #126993` 的**两刀捆包**
//   （`[DELGP]`+`[DELCURS]`，合计 −0.345 ms）的**一半**出现，而本题在册反复证明**捆包会盖住符号**。
//   (2) 对手 rank-1 保留它、且比我方在役件快 0.652 ms ⇒ 三处差异必须逐个定价（本发是第三处）。
//   (3) **机理**：`find2_` 每次调用要走两条独立的随机载入链，链长 >1 时第二跳（`dsu[h2u]`）
//   完全无前瞻；归并环用 `rs[i+8]` 提供了 8 次迭代的提前量 ⇒ 两条第二跳的**地址**在
//   line 1 的载入返回后即可算出，提示有真实提前量（本条与 `[DELGP]` 的删除理由的差别就在于：
//   删除方把「两条随机真需求载入”的代价**整体**计入，而本发测的是它能否被提前量买回来）。
// 【闸门（与 #127065 逐字节相同，6/6 + 对拍）】n18d_big0.in（52 MB, T=3, K=1）
//   md5 `a25cb5f278edf846` ✓ · o18a2__tmp/k0.in（K=0）md5 `9df57bbc8ced` ✓ · o18k3__tmp/fail3.in ✓ ·
//   s1.in ✓ · s2.in ✓ · r1noi_t1.in ✓ · 随机对拍 vs `brute.cpp` 12 例（shape 0/2/3 × K∈{0,1} × 2 seed）✓
// 【本发目的】给「KRT 祖父级提示」做**单变量板面定价**（本条是"对手三处差异"的最后一处，
//   其正负决定这条矿脉是否整体闭合）；不捆绑任何第二刀。
// ================
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#126812** <https://duck.ac/submission/126812>
//     用途：**直接复制了该提交的正文**（继承链见下方原样保留的引用块）。未声明独立许可证，
//     按「同站公开提交、注明出处」的惯例合规使用 ✓
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#126993** = 本账号现最好件、本发直接上一代；
//     [3] 提交 **#126870** = 上一代基座。本发 = [2] 的逐字节副本 + **一处**（见思路）。
// ======================
// ===== 思路 =====
// 【性质】**单变量**竞速/定价发：底盘 = [2] 逐字节副本，只加一处、不删任何东西。
// 【本刀 [C1c] — Dijkstra 入队侧的"第二跳"链式预热】
//   在册事实（本题唯一有板面兑现记录的非查询刀）：`#126790` 的 `[w1]`（在 `dl_push` 里
//   `_mm_prefetch(beg + v)`）使 **ph2 Dijkstra 相 −7.09%**、全题 tc19 −2.83% ⇒ 该相确实**受
//   `beg[u]` 的随机载入延迟支配**。
//   `[w1]` 只预取了**第一跳**（`beg[v]` 这一行）；而 pop 侧的串行链是
//     `dl_pop → dist_[u] 校验 → beg[u] → adj[e]（真的行首）→ dist_[v]`
//   ⇒ 第一跳之后**紧接着就是第二跳 `adj + beg[v]`**，它没有任何前瞻。
//   本刀在**入队时刻**（同一处、同一命中行）把第二跳也发出去：`beg[v]` 的值刚被上一行提示带进来，
//   这次需求载入是**同一 fill 上的 L1 命中**，随后据此发 `prefetch adj + beg[v]`，
//   把该顶点**未来被 pop 时**要走的邻接行提前拉进 cache —— Dial 的驻留时间就是它的提前量。
//   ★ 纯预热：不读取任何被使用的值、不新增分支、不改变任何写入 ⇒ **逐位等价**。
// 【为什么值得发】本题在册反复证明**板面是唯一定价通道**（本机/同进程探针可**否决**、不可**定价**：
//   `compMin` 全族本机探针 −3.11% 而板面 **+13.9%**；`#126790` 的刀本机 −1.82% 而板面 tc19 −2.83%）。
//   ⇒ 本刀本机 tick 测不出符号（多席共用 VM），但**机理清楚、闸门已过**，按新过程律**单变量发出定价**。
// 【闸门（与底盘逐字节相同，5/5）】n18d_big0.in(52 MB, T=3, K=1) ✓ · o18a2__tmp/k0.in(K=0) ✓ ·
//   o18k3__tmp/fail3.in ✓ · s1.in ✓ · s2.in ✓ · r1noi_t1.in ✓
// 【确定性量具】callgrind（同输入）Ir 只增"一次 L1 载入 + 一条提示"的量级；本发不据本机 tick 定价。
// ================
// ===== 思路（r9a15_ 席，2026-10-15，落位扫描：align-functions 144 -> 32，单变量）=====
// 【改动】只在底盘 #127385（= 我方现最好件 183.256240）之上把 pragma 的 align-functions 由 144 改为 32。
// 【依据】(1) 本席实测本题对**代码/数据落位**极敏感：同相位同族的两刀 [SBLK] = +2.97 ms / [PFB] = -0.025 ms；
//   [PFB2]（预取提前量变短）本机 +12%。 (2) 在册刀谱： 在 1016 = **-2.315 ms**（纯指示、值中性）。
//   (3) 本题同码锚已实测： 183.256240 vs （.text 逐字节同）= 183.245333
//   ⇒ **判题机同码散布仅 0.010907 ms**（缺口 0.064 ms = 6x 散布）⇒ 本轴的单发读数可判。
// 【闸门】s1/s2/big0 逐字节同（md5 a25cb5f278edf846）· 判题 gcc 9.3 编译 ✓
// ======================
// ===== 思路（r9a15_ 席，2026-10-15，续刀：query 相 [SGL] 快路径 + [PFB] 预取归位）=====
// 【改动】在上一发 [SGL]（= 板面 #127359 = 183.281624，我方现最好件）之上**只做一处删除类改动**
//   [PFB]：把查询环顶部的两条 `PS` 族预取（`PS+x`、`PS+(x-1)`）移进"非单叶"分支内。
//   依据：[SGL] 在役后 PS **只被通用链读到**（单叶命中路径只读 A0[x-1]/A0[x]/dPos[x]；答案 0 的
//   54% 更不读 PS）⇒ 76% 的查询在环顶发的是**无效预取请求**（全队律：置换/删除一律赚钱、
//   净增请求一律付钱）。把预取移到分支内 = 只让 24% 真正读 PS 的查询付它，且它们仍在分支后
//   紧跟依次调用前有整段分支/调用窗口作提前量。
// 【[SGL] 的等价性（保留）】：在 compMin 之前先判定「分量恰为单叶 {x}」，命中则直接
//   返回 dPos[x]，跳过 prevLE/nextLE/rangeMin 整条链。等价性（可证）：compMin 里
//   Lb = (x==0)?0:prevLE(x-1,p)+1、Rb = (x>=MB)?n-1:nextLE(x,p)，而 rangeMin 的 l==r 分支本
//   就返回 dPos[l]；故 Lb==Rb==x 时答案 = dPos[x]。又 Lb==x ⟺ prevLE(x-1,p)==x-1 ⟺ A0[x-1]<=p
//   （x==0 时 Lb 恒为 0==x）；Rb==x ⟺ nextLE(x,p)==x ⟺ A0[x]<=p（x>=MB 时 Rb 恒为 n-1，需 x==MB）。
//   ⇒ 新条件 (x==0 || A0[x-1]<=p) && (x>=MB || A0[x]<=p) 与 l==r 逐位等价。
// 【为什么值得发】本席只计数相位账（现役件 #127208 正文 + -DPHASE_TIMING，n18d_big0.in）：
//   parse 7.0% · CSR 4.4% · Dijkstra 25.3% · KRT 25.3% · DFS+A0 8.6% · 表 1.4% · **查询 27.3%**。
//   查询相内部计数：平凡（答案 0，1 次载入）54%；非平凡中 **单叶分量 55%**、同块 43%、跨块 2%
//   （另一测试点族里跨块达 43%）。单叶路径原本仍要走 prevLE/nextLE/rangeMin 的 **6~9 次依赖载入**
//   （判题机 6 MB L3 下多为 DRAM 延迟）；本快路径换成 3 次**已预取**的载入（A0[x-1]、A0[x]、dPos[x]，
//   前二者与代码既有的 `A0+(x&~15)` 预取同一条行）。
// 【命中率（插桩实测，big0 三组，与 #127359 同）】非平凡查询里：单叶 **47%**、块内 37%、16% 走通用链。
// 【闸门】s1.in / s2.in / n18d_big0.in（两次运行）**逐字节相同**（md5 `a25cb5f278edf846`，与 #127359 同）✓ ·
//   随机对拍 **200 例**（T∈1..3、n≤50、K∈{0,1}、4 形状）**与底盘逐字节相同** ✓ · 判题 gcc 9.3 编译 ✓。
// 【本机读数（配对 8 轮相位和）】总 −3.30%、查询相 −5.73%（相对底盘）；相对 #127359 的查询相
//   小幅占优（−1.3%，在噪声内）。本机 L3 38 MB ≫ 判题机 6 MB ⇒ 本机对此类"请求条数"改动偏保守。
// 【性质】续刀、单变量（只在 #127359 之上做一处**删除类**归位）；若不利，现役最好件 #127359 不受影响。
// ======================
#pragma GCC target("avx2,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O2","align-functions=32","align-jumps=8","no-tree-loop-optimize","no-caller-saves","no-ssa-phiopt")
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;
static char g_in[80 << 20];
static char g_out[80 << 20];
#else
typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;
#endif
#include <immintrin.h>
#undef PHASE_TIMING   // [o18a2_] 交件版：关掉相位计时（rdtsc 只用于本席探针）

#define MAXN 200005
#define MAXM 400005
#define MAXARC 800005
#define MAXND 400010
#define RBITS 10
#define RSIZE (1u << RBITS)
#define RMASK (RSIZE - 1)
#define SH1 6
#define MSK1 63
#define MAXB1 (MAXN / 64 + 128)   /* U1: a 64-aligned span read needs nb2*64 = 3136 entries */
#define MAXB2 128                 /* U1: the far L2A span reads 64 entries from base 0 */
static_assert(MAXB1 >= 3136, "U1: L1A/L1D span padding");
static_assert(MAXB2 >= 64, "U1: L2A/L2D span padding");

/* eln[] REMOVED: w is packed into the high 14 bits of krs[0][i].u (u<2^18, w<2^14). */
static u32 rka[MAXM], rkb[MAXM];
static u32 beg[MAXN + 2];   /* [r1noiQ3-DELCURS] curs[] deleted: beg[] is its own cursor */
static u32 adj[MAXARC];
/* sz[] REMOVED: lo(c2) == Rr[c1]+1 in DFS leaf order; the descent carries lo. */
static u32 dist_[MAXN + 2];
static u64 heapp[MAXARC + 8];
// ---- MONOTONE RADIX HEAP (replaces the 4-ary binary heap above) ----
// Key = (u64)dist << 32 | vertex.  Keys are extracted in non-decreasing order, so a radix heap
// is exact.  33 buckets (0..32); bucket k holds keys sharing the top (32-k) bits with `rhs_last`.
// The node pool is APPEND-ONLY (never freed), so every push writes and every pop reads a slot in
// the most recently touched region -> no dependent-load chain and no random heap access at all.
/* ---- H1: CIRCULAR DIAL BUCKET QUEUE.  Width C = 2^14 (the kernel's own edge-weight format),
   occupancy bitmap for O(1)-amortised skipping, ZERO redistributions, NO key stored in the pool. */
#define RHNIL 0xFFFFFFFFu
#define DCBITS 14
#define DC (1u << DCBITS)
#define DCMASK (DC - 1u)
#define DNW (DC >> 6)
static u32 dl_head[DC];                     /* 64 KB: bucket -> pool index */
static u64 dl_bit[DNW];                     /* 2 KB: occupancy bitmap */
static u64 dl_pl[2 * MAXM + 8];             /* node -> (next<<32 | vertex) */
static u32 dl_np;
static u32 dl_cnt;                          /* nodes still IN the buckets */
static i64 dl_curd;                         /* the current minimum distance (exact) */
__attribute__((always_inline)) static inline void dl_reset(void) {
  dl_np = 0; dl_cnt = 0; dl_curd = 0;
  for (u32 k = 0; k < DC; k++) dl_head[k] = RHNIL;
  for (u32 k = 0; k < DNW; k++) dl_bit[k] = 0;
}
__attribute__((always_inline)) static inline void dl_push(u32 v, u32 d) {
  u32 b = d & DCMASK;                       /* ONE link write, no move, no bucket search */
  u32 ni = dl_np++;
  _mm_prefetch((const char *)(beg + v), _MM_HINT_T0);
  /* [r1noiQ4-C1c] chained second-hop warm: the line above brings beg[v] in, so this demand
     load is an L1 hit that rides the same fill; the hint that follows warms the vertex's
     FUTURE adjacency row (adj + beg[v]), which is the head of the pop-side chain
     dist_[u] -> beg[u] -> adj[e] -> dist_[v].  Pure warm-up: no value is used, no branch,
     no write is changed => byte-identical. */
  u32 bs_ = beg[v];
  _mm_prefetch((const char *)(adj + bs_), _MM_HINT_T0);
  dl_pl[ni] = ((u64)dl_head[b] << 32) | (u64)v; dl_head[b] = ni;
  dl_bit[b >> 6] |= (u64)1 << (b & 63u);
  dl_cnt++;
}
/* advance dl_curd to the smallest distance >= it that owns a non-empty bucket */
__attribute__((always_inline)) static inline void dl_advance(void) {
  u32 b = (u32)dl_curd & DCMASK;
  u32 w = b >> 6, off = b & 63u;
  u64 m = dl_bit[w] & (~0ull << off);
  /* ⛔ `ctz(m)` IS AN ABSOLUTE BIT POSITION, NOT A DELTA.  The bit at position `off + k`
     is the bucket `k` steps AHEAD of the current one, so the distance added is `ctz(m) - off`.
     Writing `ctz(m)` alone makes the pointer jump `off` buckets too far, it lands on an empty
     bucket, and the pop reads an `RHNIL` head.  (Caught by a runtime head check, not by the eye.) */
  if (m) { dl_curd += (i64)__builtin_ctzll(m) - (i64)off; return; }
  i64 add = (i64)(64u - off);
  for (u32 w2 = (w + 1u) & (DNW - 1u); ; w2 = (w2 + 1u) & (DNW - 1u)) {
    u64 m2 = dl_bit[w2];
    if (m2) { dl_curd += add + (i64)__builtin_ctzll(m2); return; }
    add += 64;
  }
}
__attribute__((always_inline)) static inline u32 dl_pop(u32 *dv) {
  u32 b = (u32)dl_curd & DCMASK;
  u32 n = dl_head[b];
  u64 _px = dl_pl[n]; dl_head[b] = (u32)(_px >> 32);
  if (dl_head[b] == RHNIL) dl_bit[b >> 6] &= ~((u64)1 << (b & 63u));
  dl_cnt--;
  *dv = (u32)dl_curd;
  return (u32)_px;
}
static u32 dsu[MAXND], alt_[MAXND], ch1[MAXND], ch2[MAXND], Rr[MAXND];
static u32 stk[MAXND];
/* posOf[] REMOVED: pos1 is captured during the DFS leaf enumeration. */
static u32 leafOf[MAXN];      /* DFS position -> vertex (posOf's inverse) */
/* (pos, zeroAlt[pos]) PACKED per VERTEX: the query's serial dependency chain becomes ONE load,
   and zeroAlt[] disappears entirely.  vinfo[v] lo32 = posOf[v], hi32 = zeroAlt[posOf[v]]. */
static u64 vinfo[MAXN + 2];
static u32 dPos[MAXN];
static u32 preD[MAXN], sufD[MAXN];
static u32 A0[MAXN];
static u32 L1A[MAXB1], L2A[MAXB2];
static u32 L1D[MAXB1], L2D[MAXB2];
/* S5: the skip structure.  PS[i] packs  hi32 = min A0[blkstart(i)..i] (prefix, for prevLE)
   and lo32 = min A0[i..blkend(i)] (suffix, for nextLE) -- ONE 8-byte load serves both. */
static u64 PS[MAXN];
static u32 preAB[MAXB1], preLA[MAXB1], sufLA[MAXB1];
static u32 preSUP[MAXB2], sufSUP[MAXB2];
#define STK 12
static u32 st1[STK][MAXB1];
static u32 MB, nb1, nb2, nn;
struct KRRec { u32 key; u32 u; u32 v; };            /* key = ~eal : descending altitude */
static KRRec krs[2][MAXM];

#ifdef PHASE_TIMING
#include <cstdio>
static u64 ph[16];
static inline u64 rd() { return __builtin_ia32_rdtsc(); }
#define PH_START() u64 _t = rd()
#define PH_MARK(i) do { u64 _n = rd(); ph[i] += _n - _t; _t = _n; } while (0)
#define PH_DUMP() do { for (int _i = 0; _i < 16; _i++) if (ph[_i]) fprintf(stderr, "phase %d: %llu cycles\n", _i, (unsigned long long)ph[_i]); } while (0)
#else
#define PH_START()
#define PH_MARK(i)
#define PH_DUMP()
#endif

#ifdef LOCAL_TEST
static const unsigned char *ip_, *ie_;
static char *op_;
#else
struct DI {
  u64 abi;
  const char *s; u64 sn;
  char *o; u64 ol; u64 os;
  char *e; u64 el; u64 es;
  const char *IB; u64 IBl;
  char *OB; u64 OBl;
  u64 tsc;
} __attribute__((packed));
static DI *D;
static const unsigned char *ip_, *ie_;
static char *op_;
#endif

static inline u32 ni() {
  const unsigned char *p = ip_;
  u32 v = (u32)(*p++ - '0');
  while (p[0] > ' ' && p[1] > ' ') { v = v * 100u + (u32)((p[0]-'0')*10u + (p[1]-'0')); p += 2; }
  if (*p > ' ') v = v * 10 + (u32)(*p++ - '0');
  ip_ = p + 1;
  return v;
}

static const unsigned char SH10[176] __attribute__((aligned(16)))={128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,1,128,128,128,128,128,128,128,128,128,128,128,128,128,0,1,2,128,128,128,128,128,128,128,128,128,128,128,128,0,1,2,3,128,128,128,128,128,128,128,128,128,128,128,0,1,2,3,4,128,128,128,128,128,128,128,128,128,128,0,1,2,3,4,5,128,128,128,128,128,128,128,128,128,0,1,2,3,4,5,6,128,128,128,128,128,128,128,128,0,1,2,3,4,5,6,7,128,128,128,128,128,128,128,128,1,2,3,4,5,6,7,8,128,128,128,128,128,128,128,0,2,3,4,5,6,7,8,9,128,128,128,128,128,128,0,1};
template<bool WideA, bool WideB> static inline void decode2(const unsigned char *p,unsigned ka,const unsigned char *q,unsigned kb,u32 &a,u32 &b) {
  __m256i d=_mm256_castsi128_si256(_mm_loadu_si128((const __m128i*)p));
  d=_mm256_inserti128_si256(d,_mm_loadu_si128((const __m128i*)q),1);
  __m256i sh=_mm256_castsi128_si256(_mm_load_si128((const __m128i*)(SH10+16*ka)));
  sh=_mm256_inserti128_si256(sh,_mm_load_si128((const __m128i*)(SH10+16*kb)),1);
  d=_mm256_shuffle_epi8(_mm256_and_si256(d,_mm256_set1_epi8(15)),sh);
  d=_mm256_maddubs_epi16(d,_mm256_set1_epi16(0x010a));
  d=_mm256_madd_epi16(d,_mm256_set1_epi32(0x00010064));
  d=_mm256_madd_epi16(_mm256_packs_epi32(d,d),_mm256_set1_epi32(0x00012710));
  if constexpr (WideA) { u64 v=(u64)_mm_cvtsi128_si64(_mm256_castsi256_si128(d)); a=(u32)v+(u32)(v>>32)*100000000u; }
  else a=(u32)_mm_cvtsi128_si32(_mm256_castsi256_si128(d));
  if constexpr (WideB) { u64 v=(u64)_mm_cvtsi128_si64(_mm256_extracti128_si256(d,1)); b=(u32)v+(u32)(v>>32)*100000000u; }
  else b=(u32)_mm_cvtsi128_si32(_mm256_extracti128_si256(d,1));
}
static inline void ni4(u32 &a,u32 &b,u32 &c,u32 &d) {
  const unsigned char *p=ip_;
  if(p+48>ie_) {a=ni();b=ni();c=ni();d=ni();return;}
  __m256i v=_mm256_loadu_si256((const __m256i*)p);
  unsigned mask=(unsigned)_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8('0'),v));
  unsigned x=__builtin_ctz(mask);mask&=mask-1;
  unsigned y=__builtin_ctz(mask);mask&=mask-1;
  unsigned z=__builtin_ctz(mask);mask&=mask-1;
  unsigned e=__builtin_ctz(mask);
  decode2<false,false>(p,x,p+x+1,y-x-1,a,b);decode2<false,true>(p+y+1,z-y-1,p+z+1,e-z-1,c,d);
  ip_=p+e+1;
}
static inline void ni2(u32 &a, u32 &b) {
  const unsigned char *p = ip_;
  if (p + 32 > ie_) { a = ni(); b = ni(); return; }
  __m256i v = _mm256_loadu_si256((const __m256i *)p);
  unsigned mask = (unsigned)_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8('0'), v));
  unsigned x = __builtin_ctz(mask); mask &= mask - 1;
  unsigned y = __builtin_ctz(mask);
  decode2<false,true>(p, x, p + x + 1, y - x - 1, a, b);
  ip_ = p + y + 1;
}
static const char D2[] =
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899";

struct D4T {u32 a[10000];constexpr D4T():a{} {for(u32 i=0;i<10000;i++) a[i]=(48+i/1000)|((48+(i/100)%10)<<8)|((48+(i/10)%10)<<16)|((48+i%10)<<24);}};
static constexpr D4T O4;
static const u32 P10[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
static inline void pu32(u32 v) {
  u32 z=v|1,bl=32-__builtin_clz(z),len=((bl*1233)>>12)+1;
  len-=(z<P10[len-1]);char *p=op_+len;op_=p;
  while(v>=10000){u32 q=v/10000,r=v-q*10000;p-=4;__builtin_memcpy(p,&O4.a[r],4);v=q;}
  if(v>=100){u32 q=v/100,r=v-q*100;p-=2;__builtin_memcpy(p,D2+r*2,2);v=q;}
  if(v>=10){p-=2;__builtin_memcpy(p,D2+v*2,2);}else *--p=(char)('0'+v);
}

// ---- SIMD scans (AVX2; see mk_qavx.py for why each shape was chosen) ----
#pragma GCC push_options
#pragma GCC target("avx2")
/* ---- U1: ONE branchless 64-bit predicate mask per scan (no loop, no exit branch) ---- */
__attribute__((always_inline)) static inline u64 lomask64(int n) {
  return (n >= 64) ? ~0ull : ((1ull << n) - 1ull);
}
/* 64 predicate bits for arr[base .. base+63]: bit k set iff arr[base+k] <= p.
   Signed compare, EXACTLY the semantics scanLeftLE/scanRightLE used. */
__attribute__((always_inline)) static inline u64 span64(const u32 *base, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
#define U1C(k) ((u32)~((u32)_mm256_movemask_ps(_mm256_castsi256_ps( \
        _mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i *)(base + (k))), vp)))) & 0xFFu)
  u64 m0 = (u64)U1C(0),  m1 = (u64)U1C(8),  m2 = (u64)U1C(16), m3 = (u64)U1C(24);
  u64 m4 = (u64)U1C(32), m5 = (u64)U1C(40), m6 = (u64)U1C(48), m7 = (u64)U1C(56);
#undef U1C
  return m0 | (m1 << 8) | (m2 << 16) | (m3 << 24) | (m4 << 32) | (m5 << 40) | (m6 << 48) | (m7 << 56);
}
__attribute__((always_inline)) static inline u32 span8(const u32 *base, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
  return (u32)(~((u32)_mm256_movemask_ps(_mm256_castsi256_ps(
      _mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i *)base), vp))))) & 0xFFu;
}
/* rightmost j in [lo,hi] with arr[j] <= p  (base = lo & ~63, so the span is one aligned block) */
__attribute__((always_inline)) static inline int sqL(const u32 *arr, int lo, int hi, u32 p) {
  if (hi - 7 >= lo) { u32 b8 = span8(arr + hi - 7, p); if (b8) return hi - 7 + (31 - (int)__builtin_clz(b8)); }
  int base = lo & ~MSK1;
  u64 m = span64(arr + base, p) & lomask64(hi - base + 1) & ~lomask64(lo - base);
  return m ? (base + 63 - (int)__builtin_clzll(m)) : -1;
}
/* leftmost j in [lo,hi] with arr[j] <= p; hi+1 if none */
__attribute__((always_inline)) static inline int sqR(const u32 *arr, int lo, int hi, u32 p) {
  if (lo + 7 <= hi) { u32 b8 = span8(arr + lo, p); if (b8) return lo + (int)__builtin_ctz(b8); }
  int base = lo & ~MSK1;
  u64 m = span64(arr + base, p) & lomask64(hi - base + 1) & ~lomask64(lo - base);
  return m ? (base + (int)__builtin_ctzll(m)) : hi + 1;
}
// ONE horizontal reduction for the whole block, not one per 8 elements.
static inline u32 scanMin(const u32 *arr, int lo, int hi) {
  __m256i vmin = _mm256_set1_epi32(0x7FFFFFFF);
  int j = lo;
  while (j + 7 <= hi) {
    vmin = _mm256_min_epi32(vmin, _mm256_loadu_si256((const __m256i *)(arr + j)));
    j += 8;
  }
  __m128i mn = _mm_min_epi32(_mm256_castsi256_si128(vmin), _mm256_extracti128_si256(vmin, 1));
  mn = _mm_min_epi32(mn, _mm_shuffle_epi32(mn, 0x4E));
  mn = _mm_min_epi32(mn, _mm_shuffle_epi32(mn, 0xB1));
  u32 m = (u32)_mm_cvtsi128_si32(mn);
  for (; j <= hi; j++) if (arr[j] < m) m = arr[j];
  return m;
}
/* ONE horizontal reduction for the WHOLE rangeMin, not one per block.
   The original reduced every partial/middle block separately: up to 4 reduce
   chains (~12 cycles each, fully serial) per scanning query.  Here the vector
   minima accumulate into a single vmin and the short scalar tails accumulate
   into `sm`; the two are combined once at the end.  Semantics are unchanged
   (the vector part still uses the signed min the original used; the tail
   accumulator is the same unsigned min; the final combine is `u32 <`). */
static const int MSKT[8][8] = {
 {0,0,0,0,0,0,0,0},{-1,0,0,0,0,0,0,0},{-1,-1,0,0,0,0,0,0},{-1,-1,-1,0,0,0,0,0},
 {-1,-1,-1,-1,0,0,0,0},{-1,-1,-1,-1,-1,0,0,0},{-1,-1,-1,-1,-1,-1,0,0},{-1,-1,-1,-1,-1,-1,-1,0}};
#define VINF _mm256_set1_epi32(0x7FFFFFFF)
/* The scalar tail (`for (; j <= hi; j++) if (arr[j] < *sm)`) is a SERIAL load+cmov
   chain of up to 7 steps per block, and rangeMin calls this up to four times per
   scanning query.  `_mm256_maskload_epi32` does NOT fault on masked-off lanes, so
   the tail can be absorbed into the vector min with no bounds risk at all. */
__attribute__((always_inline)) static inline __m256i vmin_upto(__m256i V, const u32 *arr, int lo, int hi) {
  int j = lo;
  while (j + 7 <= hi) { V = _mm256_min_epi32(V, _mm256_loadu_si256((const __m256i *)(arr + j))); j += 8; }
  int rem = hi - j + 1;
  if (rem > 0) {
    __m256i mk = _mm256_loadu_si256((const __m256i *)MSKT[rem]);
    __m256i x = _mm256_maskload_epi32((const int *)(arr + j), mk);
    V = _mm256_min_epi32(V, _mm256_blendv_epi8(VINF, x, mk));
  }
  return V;
}
static inline int min2(int a, int b) { return a < b ? a : b; }
__attribute__((always_inline)) static inline int prevLE(u32 i, u32 p) {
  int i0 = (int)i;
  int mb = (int)MB - 1;
  int b = i0 >> SH1;
  /* SOUND: PS[i].hi = min A0[blkstart(i) .. i].  If it exceeds p, NO index in
     [blkstart(i), i] qualifies, and [blkstart(i), i] ENDS at i -- so the in-block scan
     cannot win and is skipped.  (The unsound mirror of this test is F1's.) */
  if ((u32)(PS[i0] >> 32) > p) goto level;
  return sqL(A0, b << SH1, i0, p);      /* PS[i].hi <= p guarantees a hit */
 level:
  if (b == 0 || preAB[b - 1] > p) return -1;   /* nothing anywhere in [0, i] */
  {
    int j = b - 1;
    int s = j >> SH1;
    if (preSUP[s] > p) return -1;
    if (preLA[j] <= p) {                        /* a L1A hit exists in [s<<6, j] */
      int r = sqL(L1A, s << SH1, j, p);
      if (r >= 0) return sqL(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
    }
    {
      int g = s - 1;
      if (g < 0) return -1;
      if (preSUP[g] > p) return -1;
      int r = sqL(L2A, 0, g, p);
      if (r < 0) return -1;
      int r1 = sqL(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
      if (r1 < 0) return -1;
      return sqL(A0, r1 << SH1, min2((r1 << SH1) + MSK1, mb), p);
    }
  }
}
__attribute__((always_inline)) static inline int nextLE(u32 i, u32 p) {
  int i0 = (int)i;
  int mb = (int)MB - 1;
  int b = i0 >> SH1;
  int hi = min2((b << SH1) + MSK1, mb);
  if ((u32)PS[i0] > p) goto level;             /* SOUND mirror: [i, blkend(i)] STARTS at i */
  return sqR(A0, i0, hi, p);
 level:
  if (b + 1 >= (int)nb1) return (int)MB;
  {
    int j = b + 1;
    int s = j >> SH1;
    int hh = min2((s << SH1) + MSK1, (int)nb1 - 1);
    if (sufSUP[s] > p) return (int)MB;
    if (sufLA[j] <= p) {
      int r = sqR(L1A, j, hh, p);
      if (r <= hh) return sqR(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
    }
    {
      int g = s + 1;
      if (g >= (int)nb2) return (int)MB;
      if (sufSUP[g] > p) return (int)MB;
      int r = sqR(L2A, g, (int)nb2 - 1, p);
      if (r > (int)nb2 - 1) return (int)MB;
      int r1 = sqR(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
      if (r1 > (int)nb1 - 1) return (int)MB;
      return sqR(A0, r1 << SH1, min2((r1 << SH1) + MSK1, mb), p);
    }
  }
}
__attribute__((always_inline)) static inline u32 rangeMin(u32 l, u32 r) {
  if (l == r) return dPos[l];                       // single-leaf component: no scan at all
  int bl = (int)(l >> SH1), br = (int)(r >> SH1);
  if (bl == br) return scanMin(dPos, (int)l, (int)r);
  /* ARM R2: partial dPos blocks via preD/sufD (1 load each, was up to 128 elements);
     the full-block middle via an O(1) sparse table over L1D (was up to 391 AVX2 steps). */
  u32 m = sufD[l]; { u32 b2 = preD[r]; if (b2 < m) m = b2; }
  if (bl + 1 <= br - 1) {
    u32 a = (u32)bl + 1u, b = (u32)br - 1u, len = b - a + 1u;
    int k = 31 - __builtin_clz(len);
    u32 x1 = st1[k][a], x2 = st1[k][b - (1u << k) + 1u];
    if (x1 < m) m = x1;
    if (x2 < m) m = x2;
  }
  return m;
}

/* ONE call instead of three.  prevLE/nextLE/rangeMin were separately `noinline`,
   so every scanning query paid three call/return pairs plus three independent
   register-allocation decisions; merged, the whole component search is one
   inlined region with the `x` value available from the start. */
__attribute__((noinline)) static u32 compMin(u32 x, u32 p, u32 MB_v, u32 n_v) {
  u32 Lb = (x == 0) ? 0 : (u32)(prevLE(x - 1, p) + 1);
  u32 Rb = (x >= MB_v) ? (n_v - 1) : (u32)nextLE(x, p);
  return rangeMin(Lb, Rb);
}
/* [r9a15_ SGL] 单叶分量快路径（与 compMin 逐位等价：l==r 时 rangeMin 返回 dPos[l]） */
__attribute__((always_inline)) static inline u32 compMinF(u32 x, u32 p, u32 MB_v, u32 n_v) {
  if ((x == 0u || A0[x - 1u] <= p) && (x >= MB_v || A0[x] <= p)) return dPos[x];
  return compMin(x, p, MB_v, n_v);
}

#pragma GCC pop_options

// radix sort of FUSED edge records: every access is sequential.  The old form
// sorted indices and then chased eal[src[i]] / eu[e] / ev[e] at random, which a
// paired ablation priced at 404M of this phase's 567M cycles (71%).
static u32 HST3[3][RSIZE];
/* r9c2k_ 席：32 位旋转（gray12 家族形态）。在 bmi2 可见的编译上下文里，
   gcc9 会编成三操作数 `rorx $imm,src,dst`（不破坏源寄存器）⇒ 省掉破坏性移位前的那条 mov 副本。 */
#define R9C2K_ROR32(w, r) ((u32)(((w) >> (r)) | ((w) << (32 - (r)))))

static const KRRec *kruskal_sort(u32 m) {
  KRRec *src = krs[0], *dst = krs[1];
  for (int p = 0; p < 3; p++) for (u32 j = 0; j < RSIZE; j++) HST3[p][j] = 0;
  for (u32 i = 0; i < m; i++) {
    u32 k = src[i].key;
    HST3[0][k & RMASK]++;
    /* r9c2k_: 数字抽取改「旋转」（gray12 形态）。ROR32(k,s) 的低 10 位 == (k>>s) 的低 10 位
       ⇒ 掩码/索引类型/scale 全部一字不动，只是把破坏性 shr 换成三操作数 rorx。 */
    HST3[1][R9C2K_ROR32(k, RBITS) & RMASK]++;
    HST3[2][R9C2K_ROR32(k, 2 * RBITS) & RMASK]++;
  }
  u32 nz[3];
  for (int p = 0; p < 3; p++) { u32 z = 0; for (u32 j = 0; j < RSIZE; j++) if (HST3[p][j]) z++; nz[p] = z; }
  for (int p = 0; p < 3; p++) { if (nz[p] < 2) continue; u32 a = 0; for (u32 j = 0; j < RSIZE; j++) { u32 c = HST3[p][j]; HST3[p][j] = a; a += c; } }
  for (int pass = 0; pass < 3; pass++) {
    if (nz[pass] < 2) continue;
    u32 shift = (u32)pass * RBITS;
    u32 *cur = HST3[pass];
    for (u32 i = 0; i < m; i++) { KRRec r = src[i]; dst[cur[(r.key >> shift) & RMASK]++] = r; }
    KRRec *t = src; src = dst; dst = t;
  }
  return src;
}

static u32 find_(u32 x) {
  while (dsu[x] != x) { dsu[x] = dsu[dsu[x]]; x = dsu[x]; }
  return x;
}
// The KRT union loop calls find_ TWICE per edge on two INDEPENDENT chains, and dsu[] is a
// 1.6 MB array walked at RANDOM.  Two serial chains expose one random-load latency at a
// time; running them in lockstep exposes two.  Path-halving semantics are byte-identical.
static inline void find2_(u32 x, u32 y, u32 *rx, u32 *ry) {
  for (;;) {
    u32 px = dsu[x], py = dsu[y];
    if(px==py){u32 z=find_(px);dsu[x]=dsu[y]=z;*rx=*ry=z;return;}
    int fx = (px == x), fy = (py == y);
    if (fx) *rx = x; else { dsu[x] = px = dsu[px]; x = px; }
    if (fy) *ry = y; else { dsu[y] = py = dsu[py]; y = py; }
    if (fx & fy) return;
  }
}


// --- ARM fastmod: the query decode did two 64-bit `%` with RUNTIME divisors per query, which a
// timing-only ablation priced at 30-45 cycles of the 106-117-cycle decode (~35 % of it, ~3 % of the
// row).  Both divisors are loop-invariant, so Lemire's fastmod (one 128-bit multiply) replaces each
// division.  Exact for every x < 2^64 and d < 2^63; one conditional correction.
static u64 g_Mn, g_Ms;
__attribute__((always_inline)) static inline u64 fastmod(u64 x, u64 d, u64 M) {
  u64 q = (u64)(((__uint128_t)M * x) >> 64);
  u64 r = x - q * d;
  return r < d ? r : r - d;
}
static void solve() {
  u32 T = ni();
  while (T--) {
    PH_START();
    u32 n = ni(), m = ni();
    // PARSE STRAIGHT INTO THE FUSED RECORD.  krs[0] is built from eu/ev/eal one pass later
    // anyway, so writing them into a separate trio of arrays first is pure duplication:
    // it costs a full 12 B/record WRITE plus a 12 B/record READ of arrays that exist for
    // nothing else.  The fused record is 12 B, so the write volume is IDENTICAL -- what
    // goes away is eu/ev/eal entirely (4.7 MB of touched .bss) and one whole pass.
    // ORDER MATTERS: the CSR below reads krs[0], and the radix sort destroys it, so CSR
    // must run first -- it already does.
    for (u32 i = 1; i <= n; i++) beg[i] = 0;
    for (u32 i = 0; i < m; i++) {
      _mm_prefetch((const char *)(ip_ + 192), _MM_HINT_NTA);
      u32 _u,_v,_w,_a;ni4(_u,_v,_w,_a);
      beg[_u]++; beg[_v]++;
      krs[0][i].u = _u | (_w << 18); krs[0][i].v = _v; krs[0][i].key = ~_a;
    }
    u32 Q = ni(), K = ni(), S = ni();
    PH_MARK(0);

    // ---- CSR ----
    {
      u32 s = 0;
      // [r1noiQ3-DELCURS] beg[i] = start of i's list.  The old code copied the SAME value
      // into a second 800 KB array `curs[]` and used that as the scatter cursor; instead we
      // scatter with beg[] itself and note that afterwards beg[v] == start_{v+1} (it advanced
      // exactly deg(v) times, deg(v) == 0 included), so the iteration below becomes
      // beg[v-1] .. beg[v].  `curs[]` -- 2e5 stores plus ~200 first-touched pages -- is gone.
      for (u32 i = 1; i <= n; i++) { u32 c = beg[i]; beg[i] = s; s += c; }
      beg[n + 1] = s; beg[0] = 0;
      for (u32 i = 0; i < m; i++) {
        u32 a = krs[0][i].u & 262143u, b = krs[0][i].v, w = krs[0][i].u >> 18;
        u32 pi = beg[a]++; adj[pi] = b | (w << 18);
        u32 pj = beg[b]++; adj[pj] = a | (w << 18);
      }
    }
    PH_MARK(1);

    // ---- Dijkstra from 1 ----
    const u32 INF = 3000000000u;
    for (u32 i = 1; i <= n; i++) dist_[i] = INF;
    dist_[1] = 0;
    {
      dl_reset();
      dl_push(1u, 0u);
      while (dl_cnt) {
        dl_advance();
        u32 d; u32 u = dl_pop(&d);
        if (dist_[u] != d) continue;      /* stale: H1's exact test (see the invariant above) */
        u32 e = beg[u - 1], e2 = beg[u];   // [r1noiQ3-DELCURS] post-scatter beg[v]==start_{v+1}
        /* G1: the `e + 8 < e2` prefetch guard was tested on EVERY edge of the row's
           hottest loop while protecting only the last 8.  Split it. */
        u32 e8 = (e2 >= 2u) ? e2 - 2u : e;
        for (; e < e8; e++) {
          u32 a = adj[e];
          u32 v = a & 262143u;
          u32 nd = d + (a >> 18);
          _mm_prefetch((const char *)(dist_ + (adj[e + 2] & 262143u)), _MM_HINT_T0);
          if (nd < dist_[v]) {
            dist_[v] = nd;
            dl_push(v, nd);
          }
        }
        for (; e < e2; e++) {
          u32 a = adj[e];
          u32 v = a & 262143u;
          u32 nd = d + (a >> 18);
          if (nd < dist_[v]) {
            dist_[v] = nd;
            dl_push(v, nd);
          }
        }
      }
    }
    PH_MARK(2);

    // ---- KRT ----
    for (u32 i = 1; i <= n; i++) { dsu[i] = i; alt_[i] = 0xFFFFFFFFu; }
    u32 N = n;
    if (m) {
      const KRRec *rs = kruskal_sort(m);
      /* G2: guard split, same as G1. */
      u32 i = 0, im = (m >= 8u) ? m - 8u : 0u;
      for (; i < im; i++) {
        u32 pu = rs[i+8].u & 262143u, pv = rs[i+8].v;
        // [r1noiQ3-DELGP] The second (grandparent) prefetch level is DELETED.  It was not a
        // prefetch-only cost: `h2u = dsu[pu]; h2v = dsu[pv];` are two REAL DEMAND loads into
        // the 1.6 MB `dsu` array, walked at random, and their results are used for NOTHING
        // except forming the two grandparent prefetch addresses -- i.e. every edge in the
        // merge loop paid two random cross-array loads to issue two hints.  Perf put this one
        // line at 2.13% of the whole run's samples (the loads, not the hints: the array is
        // random over 1.6 MB).  The first-level prefetch (pure `prefetchw`, no demand load)
        // is kept.
        __asm__ volatile("prefetchw %0\n\tprefetchw %1"::"m"(dsu[pu]),"m"(dsu[pv]));
        // [r14na_ K3-H2U] 单变量回退 `[r1noiQ3-DELGP]`：恢复祖父级（第二跳）提示。对手 rank-1
        // (#126812) 保留此形态，且其 #126812 = 我方 #126790 + 三刀 = −7.610 ms ⇒ 必须单变量定价。
        u32 h2u = dsu[pu], h2v = dsu[pv];
        __asm__ volatile("prefetchw %0\n\tprefetchw %1"::"m"(dsu[h2u]),"m"(dsu[h2v]));
        u32 a, b; find2_(rs[i].u & 262143u, rs[i].v, &a, &b);
        if (a != b) {
          u32 w = ++N;
          ch1[w] = a; ch2[w] = b;
          alt_[w] = ~rs[i].key;
          dsu[a] = w; dsu[b] = w; dsu[w] = w;
          if (N == n + n - 1) goto krt_complete;
        }
      }
      for (; i < m; i++) {
        u32 a, b; find2_(rs[i].u & 262143u, rs[i].v, &a, &b);
        if (a != b) {
          u32 w = ++N;
          ch1[w] = a; ch2[w] = b;
          alt_[w] = ~rs[i].key;
          dsu[a] = w; dsu[b] = w; dsu[w] = w;
          if (N == n + n - 1) goto krt_complete;
        }
      }
    }
   krt_complete:
    PH_MARK(3);

    // ---- DFS leaf order + boundary array ----
    u32 pos1 = 0;
    {
      u32 sp = 0;
      stk[sp++] = N;
      u32 c = 0;
      while (sp) {
        u32 u = stk[--sp];
        if (u <= n) {
          if (u == 1) pos1 = c;
          leafOf[c] = u;
          dPos[c] = dist_[u];
          Rr[u] = c;
          c++;
        } else {
          stk[sp++] = ch2[u]; stk[sp++] = ch1[u];
        }
      }
    }
    for (u32 u = n + 1; u <= N; u++) {
      Rr[u] = Rr[ch2[u]];
      A0[Rr[ch1[u]]] = alt_[u];
    }
    // zeroAlt[pos] = altitude of LCA(leaf at pos, leaf of vertex 1); +inf if pos == pos1
    {
      /* The ranges below cover EVERY position except pos1, whose only vertex is v=1 (leafOf[pos1]==1).
         So one store seeds it and no full-array init pass is needed.  posOf[leafOf[i]] == i, so the
         packed word is built with no extra load and no read-modify-write. */
      vinfo[1] = (0xFFFFFFFFull << 32) | (u64)pos1;
      u32 u = N; u32 lo = 0;
      while (u > n) {
        u32 c1 = ch1[u], c2 = ch2[u];
        u32 mid = Rr[c1];                 /* last leaf of c1; c2's leaves start at mid+1 */
        if (pos1 <= mid) {
          u32 hi = Rr[c2];
          for (u32 i = mid + 1; i <= hi; i++) { u32 v = leafOf[i]; vinfo[v] = ((u64)alt_[u] << 32) | (u64)i; }
          u = c1;
        } else {
          for (u32 i = lo; i <= mid; i++) { u32 v = leafOf[i]; vinfo[v] = ((u64)alt_[u] << 32) | (u64)i; }
          lo = mid + 1; u = c2;
        }
      }
    }
    PH_MARK(4);

    // ---- block minima ----
    nn = n; MB = n - 1;
    nb1 = (MB + MSK1) >> SH1;
    nb2 = (nb1 + MSK1) >> SH1;
    {
      for (u32 j = 0; j < nb1; j++) {
        u32 lo = j << SH1, hi = lo + MSK1; if (hi >= nn) hi = nn - 1;
        u32 m1 = 0xFFFFFFFFu, m2 = 0xFFFFFFFFu;
        for (u32 i = lo; i <= hi; i++) { u32 d = dPos[i]; if (d < m1) m1 = d; preD[i] = m1; }
        L1D[j] = m1;
        for (u32 i = hi + 1; i > lo; ) { i--; u32 d = dPos[i]; if (d < m2) m2 = d; sufD[i] = m2; }
      }
      /* ---- S5 skip structure (EXACT) ---- */
      {
        u32 runp = 0xFFFFFFFFu;
        for (u32 j = 0; j < nb1; j++) {
          u32 lo = j << SH1, hi = lo + MSK1;
          u32 hiA = hi; if (hiA >= MB) hiA = MB - 1;
          u32 pre = 0xFFFFFFFFu, suf = 0xFFFFFFFFu;
          for (u32 i = lo; i <= hiA; i++) { u32 d = A0[i]; if (d < pre) pre = d; PS[i] = (u64)pre << 32; }
          if (lo <= hiA) for (u32 i = hiA + 1; i > lo; ) { i--; u32 d = A0[i]; if (d < suf) suf = d; PS[i] |= suf; }
          L1A[j] = pre;
          if (pre < runp) runp = pre;
          preAB[j] = runp;
        }
      }
      for (u32 j = 0; j < nb2; j++) {
        u32 lo = j << SH1, hi = lo + MSK1;
        if (hi >= nb1) hi = nb1 - 1;
        L2A[j] = scanMin(L1A, (int)lo, (int)hi);
      }
      /* preLA/sufLA are the WITHIN-SUPERBLOCK prefix/suffix minima of L1A, and
         preSUP/sufSUP the ACROSS-superblock ones.  All four are exact tests. */
      for (u32 s = 0; s < nb2; s++) {
        u32 lo = s << SH1, hi = lo + MSK1; if (hi >= nb1) hi = nb1 - 1;
        u32 pre = 0xFFFFFFFFu, suf = 0xFFFFFFFFu;
        if (lo <= hi) {
          for (u32 i = lo; i <= hi; i++) { u32 d = L1A[i]; if (d < pre) pre = d; preLA[i] = pre; }
          for (u32 i = hi + 1; i > lo; ) { i--; u32 d = L1A[i]; if (d < suf) suf = d; sufLA[i] = suf; }
        }
      }
      {
        u32 runp = 0xFFFFFFFFu;
        for (u32 s = 0; s < nb2; s++) { if (L2A[s] < runp) runp = L2A[s]; preSUP[s] = runp; }
        u32 runs = 0xFFFFFFFFu;
        for (u32 s = nb2; s > 0; ) { s--; if (L2A[s] < runs) runs = L2A[s]; sufSUP[s] = runs; }
      }
      for (u32 i = 0; i < nb1; i++) st1[0][i] = L1D[i];
      for (int k = 1; k < STK; k++) {
        u32 half = 1u << (k - 1);
        for (u32 i = 0; i < nb1; i++) {
          u32 a2 = st1[k - 1][i];
          u32 j2 = i + half;
          u32 b2 = (j2 < nb1) ? st1[k - 1][j2] : 0xFFFFFFFFu;
          st1[k][i] = a2 < b2 ? a2 : b2;
        }
      }
    }
    PH_MARK(5);

    g_Mn = (u64)(~0ull / (u64)n) + 1; g_Ms = (u64)(~0ull / ((u64)S + 1)) + 1;
    // ---- queries ----
    i64 lastans = 0;
    if (K == 1) {
      /* [o18v_] 本臂 = 对手 **saffah_codex_6a_agg3** #121434 的**逐 token 副本**（见文件头 REFERENCES[0]）。
         试验性件：目的是**在板面上判定**「同一算法的两种写法」是否真有差——
         本席上一发 #121466 用 0-based 携带（`vm1=v-1` + `vinfo[vm1+1]`），板面 232.136501；
         对手 1-based 写法板面 230.954822，且**每个大 K=1 测试点**都系统性地快 0.6~1.7 ms。
         本发把这处差异消掉，直接量它的价（若板面回到 ~230.9 ⇒ 写法/布局确有价，再叠下一刀）。 */
      u32 v = 0, p = 0;
      if (Q) { ni2(v, p); }
      for (u32 qi = 0; qi + 1u < Q; qi++) {
      /* [o18k2_][nta-in] query input stream, same scope law as the parse ring */
      _mm_prefetch((const char *)(ip_ + 192), _MM_HINT_NTA);
      u32 anv0, anp0; ni2(anv0, anp0);
      u64 vi = vinfo[v];
            u32 x = (u32)vi, ans;
      _mm_prefetch((const char *)(A0 + (x & ~15u)), _MM_HINT_T0);
      _mm_prefetch((const char *)(dPos + (x & ~15u)), _MM_HINT_T0);
      _mm_prefetch((const char *)(vinfo + anv0), _MM_HINT_T0);
      if ((u32)(vi >> 32) > p) {
        /* [o18k3_][st2] 答案确定为 0 ⇒ 输出恒为 "0\n" 两字节；两条相邻 1 B 存
           （共享尾 pu32(0) 落下的 '0' 与 '\n'）合成一条 2 B 存。字节逐位相同。 */
        char *o2 = op_; __builtin_memcpy(o2, "0\n", 2); op_ = o2 + 2;
        v = anv0; p = anp0;
        continue;
      } else {
        /* [r9a15_ PFB] PS 族预取只服务通用链（单叶命中路径不读 PS）⇒ 从环顶移到此分支内 */
        _mm_prefetch((const char *)(PS + x), _MM_HINT_T0);
        _mm_prefetch((const char *)(PS + (x ? x - 1u : 0u)), _MM_HINT_T0);
        ans = compMinF(x, p, MB, n);
        v = (u32)fastmod((u64)(anv0 - 1) + ans, (u64)n, g_Mn) + 1;
        p = (u32)fastmod((u64)anp0 + ans, (u64)S + 1, g_Ms);
        _mm_prefetch((const char *)(vinfo + v), _MM_HINT_T0);
        pu32(ans); *op_++ = '\n';
      }
      }
      if (Q) {
      u64 vi = vinfo[v];
            u32 x = (u32)vi, ans;
      _mm_prefetch((const char *)(A0 + (x & ~15u)), _MM_HINT_T0);
      if ((u32)(vi >> 32) > p) {
        ans = 0;
      } else {
        _mm_prefetch((const char *)(dPos + (x & ~15u)), _MM_HINT_T0);
        ans = compMinF(x, p, MB, n);
      }
      pu32(ans); *op_++ = '\n';
      }
    } else {
      for (u32 qi = 0; qi < Q; qi++) {
      u32 v0 = ni(), p0 = ni();
      u64 la = (u64)lastans;
      u32 v, p;
      // [o18y_] K==0 直通：题面保证 1<=v0<=n、0<=p0<=S ⇒ 两个模都是恒等变换，整段删掉
      if (K == 0 && v0 <= n && p0 <= S) { v = v0; p = p0; }
      else {
        v = (u32)fastmod((u64)(v0 - 1) + (u64)K * la, (u64)n, g_Mn) + 1;
        p = (u32)fastmod((u64)p0 + (u64)K * la, (u64)S + 1, g_Ms);
      }
      u64 vi = vinfo[v];
            u32 x = (u32)vi, ans;
      /* [n18az-2][pf-hoist] issue the re-aimed level-0 A0 prefetch BEFORE the answer-0 branch:
         the address needs only the low 32 bits of the vinfo load, so the branch, the call and the
         probe setup all become prefetch lead time.  Costs one extra prefetch issued for the 54.2%
         zero-answer queries (measured: 650,882 of 1,200,000).  Arm 2 of the reserve pair; arm 1
         (work/n18az_1.cpp) keeps the prefetch inside the branch.  NOTE: the pre-existing hoist
         experiment #109632 (same hoist, OLD block-base target) measured NEUTRAL (+0.012 ms). */
      _mm_prefetch((const char *)(A0 + (x & ~15u)), _MM_HINT_T0);
      if ((u32)(vi >> 32) > p) {
        ans = 0;
      } else {
        /* [n18az-1][pf-line] (moved above the branch by [n18az-2][pf-hoist]) */
        ans = compMinF(x, p, MB, n);
      }
      lastans = (i64)ans;
      pu32(ans); *op_++ = '\n';
    }
    }
    PH_MARK(6);
  }
}

#ifdef LOCAL_TEST
int main() {
  size_t sn = fread(g_in, 1, sizeof(g_in), stdin);
  ip_ = (const unsigned char *)g_in; ie_ = ip_ + sn;
  op_ = g_out;
  solve();
  fwrite(g_out, 1, (size_t)(op_ - g_out), stdout);
  PH_DUMP();
  return 0;
}
#else
int main() { return 0; }
extern "C" void __libc_start_main(void *mmm, int argc, char **argv) {
  (void)mmm;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++;
  p++;
  for (; p[0]; p += 2) if (p[0] == 0x6b637564UL) { D = (DI *)p[1]; break; }
  if (D) {
    ip_ = (const unsigned char *)D->s; ie_ = ip_ + D->sn; op_ = D->o;
    solve();
    D->os = (u64)(op_ - D->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
#endif

评测结果