代码

// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125958** <https://duck.ac/submission/125958>
//     用途：**直接复制了该提交的正文** —— 本发正文 = 该公开件的逐字节副本（仅在其之上叠加本发两把刀，
//     并顺手删掉因此变成死代码的建表段；其自身继承的引用块**原样保留在下方**，未删未改）。
//     该件即本题当前 T = 198.241611 ms 的持有件；其新刀 = 「4 数一次宽取 + AVX2 并行解析（ni4/decode2/SH10）」
//     与 `#pragma GCC target("avx2,...")`（本发全部保留）。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#123274** <https://duck.ac/submission/123274>
//     用途：**直接复制了**该公开件的 **compMin 全族**：`O18K3_LDU`（单指令 32B 载入内联汇编宏）、
//     `scanLeftLE`/`scanRightLE`、`NOSCAN`/`prevProbe`/`prevFinish`/`nextProbe`/`nextFinish`、
//     `rangeMin`、`compMin`，用来整体替换 [1] 底盘里的 `lomask64`/`span64`/`sqL`/`sqR` 版本；
//     并**直接复制了**该件 `find2_` 的「同根快径」一行写法。
// [3] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#123765** <https://duck.ac/submission/123765>
//     用途：本账号自己的公开件（[1] 的底盘即由该件继承而来，经 [1] 的继承链到达本发）。
// 【许可合规】以上三件均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处；三件均未声明
//     独立许可证，故本发按「公开提交、注明出处」的惯例合规使用 ✓
// ======================
// ===== 思路 =====
// 【性质】试验性提交（目的 = 用**板面**验收判题机 gcc 9.3 上「我方 compMin 全族移植 + find2_ 同根快径」的增益）。
// 【本发 = 对手 #125958 的底盘 + 我方两把刀（各自单变量可拆）】
// 【刀 1 — [qmin] compMin 全族移植】把 [1] 底盘中的 `span64/sqL/sqR/prevLE/nextLE/compMin` 整段换成
//   [2] 的 `scanLeftLE/scanRightLE/prevProbe/prevFinish/nextProbe/nextFinish/compMin`。
//   机理（为什么更快）：底盘版 `sqL/sqR` 对**整个 64 元素块**无条件算满谓词位（8 条 32B 载入 + 8×vpcmpgtd +
//   8×vmovmskps + 8 条移位/或 ≈ 30+ uop，结果链 ≈ 25 拍）；而我方版从 `i` 起按 **8 元素步退、命中即 return**
//   （实测「A0 块内首轮命中」占探针的 ~75%）⇒ 常见情形只有 **1 条 32B 载入 + 6 条 uop、链 ≈ 15 拍**。
//   两者语义**逐位恒等**（同为「[lo,hi] 内 arr[j] <= p 的最右/最左 j」；比较用同一 signed `_mm256_cmpgt_epi32`）。
//   ★ 该方向**已由判题机探针背书**（[o18a2_]：同母体只换 compMin 的 A vs C 臂，ph6 查询相 104 拍/查询 vs 114 拍/查询）。
// 【刀 2 — [f2r] find2_ 同根快径】[1] 的引擎**丢掉了同一位对手自己 #120576 引入的快径**
//   （`if(px==py){u32 z=find_(px);dsu[x]=dsu[y]=z;*rx=*ry=z;return;}`；#120576 头部自述该改动，
//   我方在册记载其**板面单变量 −1.869 ms**）。本发把它加回，并把因此变成死代码的 skip 结构
//   （`PS[]`/`preAB[]`/`preLA[]`/`sufLA[]`/`preSUP[]`/`sufSUP[]` 的建表，只服务被换掉的底盘版 prevLE/nextLE）
//   一并删掉（只删它们的**建表**，数组声明原样保留，避免动 .bss 布局）。
// 【等价性】两把刀都不改任何数据流：刀 1 只换「同一个谓词扫描的两个实现」，刀 2 是「两条链已同根时只走一条」
//   （路径压缩语义逐位相同）；被删的建表段在替换后无任何读者。
// 【闸门（全部逐字节）】big0 三组（T=3, n=2e5 m=4e5 Q=4e5 K=1 S=1e9）md5 与底盘**逐字节相同** ✓ ·
//   K=0 小例（o18a2__tmp/k0.in）✓ · s1/s2 ✓ · **随机对拍 40 例**（tree/chain/random/sparse 四形态、n≤300、
//   K∈{0,1}、S∈{1,1e4,1e9}、T≤3）输出全同 ✓ · 判题 gcc 9.3 编译 OK ✓
// 【定价依据】刀 2 = 板面单变量 −1.869 ms（[2] 世系记载）；刀 1 = 判题机同母体探针 ph6 −8.8%（104 vs 114 拍/查询），
//   本发另用 4 臂判题机探针（base / +刀1 / +刀2 / +两刀）复核。
// ================
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/123765:
new Dial-queue/Kruskal/query engine, retaining its inherited credits below.
saffah_codex_6a_agg3 https://duck.ac/submission/120243: our accepted four-field
edge parser (based on saffah_cc_v41_agg1 #109637), reused here. No separate license.
Idea: Integrate our four-field shared delimiter scan with the newer graph
engine. Decode endpoint and weight/altitude pairs in parallel from one 32-byte
mask and advance the edge cursor once; retain the newer two-digit scalar
reader for query/header/tail fields and all newer query/Dijkstra algorithms.
Purpose: Reduce the edge parse phase in the improved algorithmic baseline.
*/
// ===== REFERENCES（[o18a2_ 席] 2026-10-03）=====
// [1] ★【母体】正文 = duck.ac 用户 **saffah_cc_v41_260924** 公开件 **#123746**
//     <https://duck.ac/submission/123746>（noi18a，217.025057 ms，Accepted，现排行榜第一 = 本题 T）
//     的**逐字节副本**；本席只叠加下列我方在册刀。
// [2] 【查询相】[carry]+[st2] = **我方** #123274 <https://duck.ac/submission/123274> 的 K=1 携带臂
//     （结构源自对手 **saffah_codex_6a_agg3** 公开件 **#121434** <https://duck.ac/submission/121434>：
//      零答案臂 v=nv0;p=np0 把两个 fastmod 整段拿走并携带到下一轮；叠加我方 [o18w_] 软件流水 + 三预取、
//      [o18k3_][st2] 零答案两 1B 存并一条 2B 存）；[o4fmt] = 我方 #123274 的 4 位表式 pu32
//     （该写法出自我方世系里的对手 saffah_codex_6s_agg2 公开件 #120531）。
// [3] 【非查询相】[dist2]/[nta]/[dsupf] 均出自我方 #123274 世系：[o18u_]（Dijkstra 弧扫前瞻 8->2）、
//     [o18k2_]（解析环输入流 prefetchnta dist=192）、[o18p_]（KRT 并查集归并环第 1/2 跳 prefetchw）。
// 【许可合规】以上均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处 ✓
// ===== 思路 =====
// ===== 本次思路（[o18a2_ 席] 2026-10-03；试验性提交，目的 = 用板面验收判题机探针测得的移植增益）=====
// 【本发 = 臂 QN（并集）】母体 #123746 + 我方查询相三刀 + 我方非查询相三刀。
// 【切入】本席角度 = 取回对手件 diff 移植。判题机探针（同 run 同输入轮转、min-of-3，源 n=1e5/m=2e5/Q=2e5）
//   实测：母体 106,874,700 拍；仅叠查询相三刀 = 100,729,766（−5.75%，其中 ph6 查询相 −6.90 M）；
//   仅叠非查询相三刀 = 103,968,354（−2.72%，其中 ph3 KRT −1.96 M、ph0 解析 −0.20 M）。
//   本发把两臂并集（四个相位互不重叠，取 min-of-3 的同一读数）交板面验收。
// 【闸门】big0.in（T=3 n=2e5 m=4e5 Q=4e5 K=1）输出 md5 `ff609130f903dbdbd0ae09f6b53e5da7` 与母体、
//   与 #123274 逐字节同 ✓ · K=0 小例（n=60 m=120 Q=5000）md5 `9df57bbc8ced1b18f42bd2f564f39c9e` 同 ✓
// · 判题 gcc 9.3 编译 OK ✓
// noi18a 【NOI2018】归程 -- v4
// Kruskal tree -> DFS leaf order -> boundary array A0[b] = merge altitude at the boundary
// between DFS-adjacent leaves b,b+1.
// component(v,p) = maximal leaf interval around x=pos[v] whose internal boundaries all have
//                  A0 > p  (a boundary with A0 <= p blocks: its merging edge is flooded).
//   L = prevLE(x-1,p)+1,  R = nextLE(x,p),  answer = min dPos[L..R]
// Searches / range-min use SIMD scans over a 3-level 64-ary block structure.
#pragma GCC target("avx2,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O2","align-functions=144","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], curs[MAXN + 2], cnt[RSIZE + 1];
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 u32 dl_pool[2 * MAXM + 8];           /* node -> vertex */
static u32 dl_nx[2 * MAXM + 8];             /* node -> next */
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++;
  dl_pool[ni] = v; dl_nx[ni] = dl_head[b]; 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];
  dl_head[b] = dl_nx[n];
  if (dl_head[b] == RHNIL) dl_bit[b >> 6] &= ~((u64)1 << (b & 63u));
  dl_cnt--;
  *dv = (u32)dl_curd;
  return dl_pool[n];
}
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};
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));
  u64 va=(u64)_mm_cvtsi128_si64(_mm256_castsi256_si128(d)),vb=(u64)_mm_cvtsi128_si64(_mm256_extracti128_si256(d,1));
  a=(u32)va+(u32)(va>>32)*100000000u;b=(u32)vb+(u32)(vb>>32)*100000000u;
}
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(p,x,p+x+1,y-x-1,a,b);decode2(p+y+1,z-y-1,p+z+1,e-z-1,c,d);
  ip_=p+e+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")
#define O18K3_LDU(p) ({ __m256i _v3; __asm__("vmovdqu %1, %0" : "=x"(_v3) : "m"(*(const __m256i *)(p))); _v3; })
static inline int scanLeftLE(const u32 *arr, int lo, int hi, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
  int j = hi;
  while (j - 7 >= lo) {
    __m256i x = O18K3_LDU(arr + j - 7);
    u32 bits = (~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x, vp)))) & 0xFFu;
    if (bits) return j - 7 + (31 - __builtin_clz(bits));
    j -= 8;
  }
  if(j>=lo){
    __m256i x=O18K3_LDU(arr+lo);
    u32 bits=(~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x,vp))))&((1u<<(j-lo+1))-1);
    if(bits)return lo+31-__builtin_clz(bits);
  }
  return -1;
}
static inline int scanRightLE(const u32 *arr, int lo, int hi, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
  int j = lo;
  while (j + 7 <= hi) {
    __m256i x = O18K3_LDU(arr + j);
    u32 bits = (~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x, vp)))) & 0xFFu;
    if (bits) return j + __builtin_ctz(bits);
    j += 8;
  }
  if(j<=hi){
    __m256i x=O18K3_LDU(arr+j);
    u32 bits=(~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x,vp))))&((1u<<(hi-j+1))-1);
    if(bits)return j+__builtin_ctz(bits);
  }
  return 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 r = scanLeftLE(A0, i0 & ~MSK1, i0, p);
  if (r >= 0) return r;
  int j = (i0 >> SH1) - 1;
  if (j < 0) return -1;
  r = scanLeftLE(L1A, j & ~MSK1, j, p);
  if (r >= 0) return scanLeftLE(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
  int g = (j >> SH1) - 1;
  if (g < 0) return -1;
  r = scanLeftLE(L2A, 0, g, p);
  if (r < 0) return -1;
  int r1 = scanLeftLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 < 0) return -1;
  return scanLeftLE(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 hi = min2((i0 & ~MSK1) + MSK1, mb);
  int r = scanRightLE(A0, i0, hi, p);
  if (r <= hi) return r;
  int j = (i0 >> SH1) + 1;
  if (j >= (int)nb1) return (int)MB;
  int h1 = min2((j & ~MSK1) + MSK1, (int)nb1 - 1);
  r = scanRightLE(L1A, j, h1, p);
  if (r <= h1) return scanRightLE(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
  int g = (j >> SH1) + 1;
  if (g >= (int)nb2) return (int)MB;
  r = scanRightLE(L2A, g, (int)nb2 - 1, p);
  if (r > (int)nb2 - 1) return (int)MB;
  int r1 = scanRightLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 > (int)nb1 - 1) return (int)MB;
  return scanRightLE(A0, r1 << SH1, min2((r1 << SH1) + MSK1, mb), p);
}
#define NOSCAN 0x40000000   /* [n18az-1] sentinel block base (real bases < nb1<<6 < 2^18) */

__attribute__((always_inline)) static inline int prevProbe(int i0, u32 p, int *l0) {
  int mb = (int)MB - 1;
  int r = scanLeftLE(A0, i0 & ~MSK1, i0, p);
  if (r >= 0) { *l0 = r; return NOSCAN; }
  int j = (i0 >> SH1) - 1;
  if (j < 0) { *l0 = -1; return NOSCAN; }
  r = scanLeftLE(L1A, j & ~MSK1, j, p);
  if (r >= 0) return r << SH1;
  int g = (j >> SH1) - 1;
  if (g < 0) { *l0 = -1; return NOSCAN; }
  r = scanLeftLE(L2A, 0, g, p);
  if (r < 0) { *l0 = -1; return NOSCAN; }
  int r1 = scanLeftLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 < 0) { *l0 = -1; return NOSCAN; }
  return r1 << SH1;
}
__attribute__((always_inline)) static inline int prevFinish(int base, int l0, u32 p) {
  if (base == NOSCAN) return l0;
  return scanLeftLE(A0, base, min2(base + MSK1, (int)MB - 1), p);
}
__attribute__((always_inline)) static inline int nextProbe(int i0, u32 p, int *l0) {
  int mb = (int)MB - 1;
  int hi = min2((i0 & ~MSK1) + MSK1, mb);
  int r = scanRightLE(A0, i0, hi, p);
  if (r <= hi) { *l0 = r; return NOSCAN; }
  int j = (i0 >> SH1) + 1;
  if (j >= (int)nb1) { *l0 = (int)MB; return NOSCAN; }
  int h1 = min2((j & ~MSK1) + MSK1, (int)nb1 - 1);
  r = scanRightLE(L1A, j, h1, p);
  if (r <= h1) return r << SH1;
  int g = (j >> SH1) + 1;
  if (g >= (int)nb2) { *l0 = (int)MB; return NOSCAN; }
  r = scanRightLE(L2A, g, (int)nb2 - 1, p);
  if (r > (int)nb2 - 1) { *l0 = (int)MB; return NOSCAN; }
  int r1 = scanRightLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 > (int)nb1 - 1) { *l0 = (int)MB; return NOSCAN; }
  return r1 << SH1;
}
__attribute__((always_inline)) static inline int nextFinish(int base, int l0, u32 p) {
  if (base == NOSCAN) return l0;
  return scanRightLE(A0, base, min2(base + MSK1, (int)MB - 1), 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) {
  int l0L = -1, l0R = (int)MB, bL = NOSCAN, bR = NOSCAN;
  if (x != 0)   bL = prevProbe((int)x - 1, p, &l0L);
  if (x < MB_v) bR = nextProbe((int)x, p, &l0R);
  /* both cold block addresses are known now: start the line each walk touches FIRST */
  if (bL != NOSCAN) { int hiL = min2(bL + MSK1, (int)MB - 1);
                      _mm_prefetch((const char *)(A0 + (hiL & ~15)), _MM_HINT_T0); }
  if (bR != NOSCAN) _mm_prefetch((const char *)(A0 + bR), _MM_HINT_T0);
  u32 Lb = (x == 0) ? 0u : (u32)(prevFinish(bL, l0L, p) + 1);
  u32 Rb = (x >= MB_v) ? (n_v - 1) : (u32)(nextFinish(bR, l0R, p));
  return rangeMin(Lb, Rb);
}
#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];
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]++; HST3[1][(k >> RBITS) & RMASK]++; HST3[2][(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;
      for (u32 i = 1; i <= n; i++) { u32 c = beg[i]; beg[i] = s; curs[i] = s; s += c; }
      beg[n + 1] = s; curs[n + 1] = s;
      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 = curs[a]++; adj[pi] = b | (w << 18);
        u32 pj = curs[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], e2 = beg[u + 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;
        __asm__ volatile("prefetchw %0\n\tprefetchw %1"::"m"(dsu[pu]),"m"(dsu[pv]));
        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;
        }
      }
      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;
        }
      }
    }
    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; }
        for (u32 i = hi + 1; i > lo; ) { i--; u32 d = dPos[i]; if (d < m2) m2 = d; sufD[i] = m2; }
      }
      for (u32 j = 0; j < nb1; j++) {
        u32 lo = j << SH1, hi = lo + MSK1;
        u32 hiA = hi; if (hiA >= MB) hiA = MB - 1;
        L1A[j] = scanMin(A0, (int)lo, (int)hiA);
        u32 loD = lo; if (loD >= n) loD = n - 1;
        u32 hiD = hi; if (hiD >= n) hiD = n - 1;
        L1D[j] = scanMin(dPos, (int)loD, (int)hiD);
      }
      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);
        L2D[j] = scanMin(L1D, (int)lo, (int)hi);
      }
      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) { v = ni(); p = ni(); }
      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 nv0 = ni(), np0 = ni();
      u64 vi = vinfo[v];
            u32 x = (u32)vi, ans;
      _mm_prefetch((const char *)(A0 + (x & ~15u)), _MM_HINT_T0);
      _mm_prefetch((const char *)(vinfo + nv0), _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 = nv0; p = np0;
        continue;
      } else {
        _mm_prefetch((const char *)(dPos + (x & ~15u)), _MM_HINT_T0);
        ans = compMin(x, p, MB, n);
        v = (u32)fastmod((u64)(nv0 - 1) + ans, (u64)n, g_Mn) + 1;
        p = (u32)fastmod((u64)np0 + 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 = compMin(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 = compMin(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

评测结果