代码

// ===== REFERENCES =====
// [1] 本件基座 = **我方**（saffah_cc_v41_agg1）提交 **#109637** 的正文 = `work/n18e_D.cpp`
//     （noi18a，279.897249 ms，Dial 环 16384）——本文件正文与该件逐字节相同，
//     仅叠加下方 [2] 的对手刀（+ 变体 b 另叠加 [o18x-V] 我方储备刀）。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120243** <https://duck.ac/submission/120243>
//     （noi18a，**277.581217 ms** = 本题实时 T）——本发从其公开件取**一条刀**：
//     正文插入 `#pragma GCC target("avx2")` + `SH10`/`ni_pair`/`decode2`/`ni4` 四个
//     AVX2 十进制成对/成四解析器，并把**边解析** `ni,ni,ni,ni` → `ni4(...)`、
//     **查询解析** `ni,ni` → `ni_pair(...)`（其头注自述同处："Decode all four edge fields
//     from one 32-byte delimiter mask ... Decode query integers in pairs"）✓
//     其余正文我方逐字节保留 ✓ 该件头注自述其正文取自我方 #109637 ✓（= §2.18.602 对手抄件史）
// 【许可合规】两件均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处 ✓
// ===== 思路 =====
// 【本发性质】`抄对手刀`：把对手 #120243 相对我方 #109637 的**真改动**（AVX2 成对解析）
//   搬回我方基座（对手的基座就是本件 ⇒ 该刀在我方的迁移是"同基座"的，无落后量问题）✓
// 【闸门】解析改写是**值等价**改写（十进制 → 同一整数）⇒ 输出应逐位不变；
//   硬闸门 `.cache/gate.sh`（最坏输入 md5 = a25cb5f278edf846f04fee1cfb82f035）由机器判 ✓
// 【目的】红题：取回对手已定价的实测增量（对手件 277.581 vs 我方 279.897 = −2.316 ms）✓
// [o18x-V] 叠加我方储备刀（`work/n18az_1.cpp`，前席已过闸门、未发）：
//   [pf-line]   查询环 A0 预取由"块基址"改瞄"含 x 的那条 line"（实测 95% 的叶块部分扫
//               在含 x 的 line 内就结束 ⇒ 旧地址 95% 瞄错）✓
//   [pf-rescan] prevLE/nextLE 拆成 probe(0..2 级, 全命中) + finish(冷块走)，两个方向的
//               probe 都做完后**背靠背**发两条复扫预取，再走两个 finish
//               （实测 152,730 次复扫 / 1.2 M 查询，每次 2.35 line）✓
//   两处均为**纯预取/纯调度** ⇒ 逐位等价是构造性的 ✓（前席已实测 GATE PASS + (189) objdump 正控）
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_cc_v41_260924**，提交 **#109344** <https://duck.ac/submission/109344>
//     （noi18a，285.264176 ms = 本题实时 T）—— **本文件正文 = 该公开件的逐字节副本**；
//     本席只在上方补引用区与说明，**正文一字未改** ✓（正文首行仍是其 `#pragma GCC target(...)`）
// [2] 其头注自述形态：Kruskal tree → DFS 叶序 → 边界数组 A0（相邻叶的合并海拔）；
//     component(v,p) = 以 pos[v] 为中心、内部边界 A0 > p 的最大叶区间；
//     L = prevLE(x-1,p)+1 · R = nextLE(x,p) · 答案 = min dPos[L..R]；
//     **搜索与区间最小走 3 级 64 叉分块的 SIMD 扫描** ✓
// [3] 依 `§2.18.349`（抄对手第一）+ `§2.19.650`：我方旧最好件 #108581（296.706 ms）系**上一代**
//     引擎；对手此发为**新世代**（285.264 ms，较其上一发 −3.9%）⇒ **整份复刻**是唯一低风险路径 ✓
// [4] duck.ac 用户 **saffah_codex_6s_agg2**，提交 **#109478** <https://duck.ac/submission/109478>
//     （noi18a，280.511206 ms = 本题实时 T）—— 本发从该公开件取**一条单变量刀**：
//     把 Kruskal 并查环的 DSU 预取地址由 `dsu + rs[i+8].u` 改为 `dsu + (rs[i+8].u & 262143u)`；
//     其头注自述同一处（"the leading vertex rs[i+8].u stores edge length in its high bits, so
//     mask to its low 18 vertex bits before prefetch"）✓ 其余正文仍逐字节等于 #109344 ✓
// 【许可合规】两件均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处；
//     本发只改一个预取操作数，未取用任何站外/闭源素材 ⇒ 合规 ✓
// ===== 思路 =====
// 【本发性质】**整份复刻**（不是单变量刀）⇒ 按纪律在此声明 ✓
// 【闸门】副本与源件的 `.text` 段字节应完全相同（本机用 `objcopy --output-target=binary
//   --only-section=.text` + md5 两侧核对 ✓）
// 【目的】把我方最好件 296.706 → ≈285.3（−3.8%），把缺口从 10.014 ms 收回 1% 手续费形态 ✓
// 【做法说明 · n18e-A（DSU 预取地址掩码）】
//   病灶：`krs[0][i].u = _u | (_w << 18)`（低 18 位顶点 · 高位边长）。并查环里预取写成
//     `_mm_prefetch(dsu + rs[i+8].u)` ⇒ **未掩码** ⇒ 预取地址 = dsu + 顶点 + 边长·2^18，
//     是一个野地址 ⇒ 对一条**占全程 26.5%（KRT 相 241 M 周期）、且是纯随机 DSU 延迟链**的
//     时段 **等于完全没有预取** ✓
//   修法：`dsu + (rs[i + 8].u & 262143u)`（18 位顶点域，与该循环内 find2_ 的取值掩码一致）✓
// 【等价精确形态】预取**不改变任何计算结果** ⇒ 与基准逐位等价是**构造性**的：
//   两条二进制在 52.8 MB 最坏输入（T=3,n=2e5,m=4e5,Q=4e5,K=1,S=1e9）上 md5 相同 =
//   a25cb5f278edf846f04fee1cfb82f035 ✓（样例 s1 亦同 ✓）
// 【臂有效性三控制】① 等价性 = 输出 md5 逐位相同（上）② **"不执行该代码"对照臂** = 把掩码去掉
//   即基准件自身（两条二进制 md5 相同 ⇒ 对照臂就是基准 ✓）③ 本地相位读数（单跑，仅方向参考，
//   本机噪声 ±8%）：KRT 相 215.7 M → 206.1 M 周期 ✓ 与机理同向
// 【目的】正式候选（非实验件）：把对手 #109478 中这条**零风险、构造性等价**的刀装到我方最好件 ✓
// ================
// [n18az-2] RESERVE ARTIFACT (arm 2 = arm 1 + pf-hoist) for noi18a (prepared, NOT submitted).  Base = work/n18e_D.cpp
// = submission #109637 ("Dial ring 16384", mine 279.897249 ms).  Two changes, both PURE
// PREFETCH -> bit-identical output BY CONSTRUCTION (see work/n18az_mk.py + restart_dossier.md).
//   [pf-line]   re-aim the query-loop A0 prefetch at the line of x (95% of level-0 scans
//               answer inside it; the old block-base address is reached by only ~5%).
//   [pf-rescan] probe/finish split of prevLE/nextLE so both cold re-scan blocks are
//               prefetched back to back before either walk (152,730 walks / 1.2 M queries).
// 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")
#pragma GCC target("bmi2,lzcnt,popcnt")
#pragma GCC optimize("O2","align-functions=144","align-jumps=8","no-tree-loop-optimize","no-caller-saves","no-ssa-phiopt")  // [a18v-placement] control: same code as #109352
#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>
#define PHASE_TIMING 1

#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 + 2)
#define MAXB2 (MAXB1 / 64 + 2)

/* 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.
#define RHNIL 0xFFFFFFFFu
/* [n18e-D] power-of-two ring: the 10001 ring forced a multiply-shift sequence for
   `d % DIAL_N` on every push (~4 uops, 788k pushes); a power-of-two ring makes it a single
   `and`.  The ring+bitset pop logic is modulus-agnostic (it already handles wraparound), so
   the extracted order is unchanged. */
#define DIAL_N 16384u
#define DIAL_WORDS ((DIAL_N + 63) / 64)
static u32 dial_head[DIAL_N], dial_next[2 * MAXM + 8], dial_vertex[2 * MAXM + 8];
static u64 dial_bits[DIAL_WORDS];
static u32 dial_np, dial_pending, dial_cur, dial_mod;
static inline void rhs_push(u64 x) {
  u32 d = (u32)(x >> 32), v = (u32)x;
  u32 b = d % DIAL_N;
  u32 ni = dial_np++;
  dial_vertex[ni] = v;
  dial_next[ni] = dial_head[b];
  dial_head[b] = ni;
  dial_bits[b >> 6] |= 1ULL << (b & 63);
  dial_pending++;
}
static inline u64 rhs_pop() {
  u32 old = dial_mod;
  u32 wi = old >> 6;
  u64 bits = dial_bits[wi] & (~0ULL << (old & 63));
  u32 b;
  if (bits) b = (wi << 6) + (u32)__builtin_ctzll(bits);
  else {
    u32 i = wi + 1;
    for (; i < DIAL_WORDS && !dial_bits[i]; i++);
    if (i < DIAL_WORDS) b = (i << 6) + (u32)__builtin_ctzll(dial_bits[i]);
    else {
      i = 0;
      for (; i <= wi && !dial_bits[i]; i++);
      b = (i << 6) + (u32)__builtin_ctzll(dial_bits[i]);
    }
  }
  dial_cur += b >= old ? b - old : DIAL_N + b - old;
  dial_mod = b;
  u32 ni = dial_head[b];
  dial_head[b] = dial_next[ni];
  if (dial_head[b] == RHNIL) dial_bits[b >> 6] &= ~(1ULL << (b & 63));
  dial_pending--;
  return ((u64)dial_cur << 32) | dial_vertex[ni];
}
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 A0[MAXN];
static u32 L1A[MAXB1], L2A[MAXB2];
static u32 L1D[MAXB1], L2D[MAXB2];
static u32 MB, nb1, nb2, nn;
#define NOSCAN 0x40000000   /* [n18az-1] sentinel block base (real bases < nb1<<6 < 2^18) */

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 > ' ') 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 ni_pair(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 ka=(unsigned)__builtin_ctz(mask),end=(unsigned)__builtin_ctz(mask&(mask-1)),kb=end-ka-1;
  __m256i d=_mm256_castsi128_si256(_mm256_castsi256_si128(v));
  d=_mm256_inserti128_si256(d,_mm_loadu_si128((const __m128i *)(p+ka+1)),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;ip_=p+end+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";

static inline void pu32(u32 v) {
  char t[12];
  int q = 0;
  while (v >= 100) {
    u32 d = v / 100, r = (v - d * 100) * 2;
    v = d;
    t[q++] = D2[r + 1]; t[q++] = D2[r];
  }
  if (v >= 10) { u32 r = v * 2; t[q++] = D2[r + 1]; t[q++] = D2[r]; }
  else t[q++] = (char)('0' + v);
  char *o = op_;
  while (q) *o++ = t[--q];
  op_ = o;
}

// ---- SIMD scans (AVX2; see mk_qavx.py for why each shape was chosen) ----
#pragma GCC push_options
#pragma GCC target("avx2")
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 = _mm256_loadu_si256((const __m256i *)(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;
  }
  for (; j >= lo; j--) if (arr[j] <= p) return j;
  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 = _mm256_loadu_si256((const __m256i *)(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;
  }
  for (; j <= hi; j++) if (arr[j] <= p) return j;
  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);
}
__attribute__((always_inline)) 
/* [n18az-1][pf-rescan]  Split prevLE/nextLE into PROBE (levels 0..2: the level-0 partial block,
   the L1A level, the L2A level -- all of them cache-resident summaries) and FINISH (the cold A0
   block walk at the block the probe selected).
   Why: the A0 block walk is the ONLY cold random access inside prevLE/nextLE and its address is
   not known until the probe finishes, so program order exposes its whole latency -- and, in the
   old form, the LEFT walk was finished before the RIGHT probe even started, so the two cold
   blocks could not be in flight together.  Both walks are driven by the same chain, and the
   right-hand probe is independent of the left-hand walk, so hoisting both probes to the front and
   issuing both block prefetches back to back starts the two cold lines together.
   `cnt` (work/n18az_cnt.cpp, run on the 52.8 MB worst-case input) sizes the target:
     1,200,000 queries, 549,118 of them scanning; A0 full-block walks = 152,730 events
     (27.8% of scanning queries), 2.35 cache lines each. */
__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);
  __m256i V = _mm256_set1_epi32(0x7FFFFFFF);
  V = vmin_upto(V, dPos, (int)l, min2((bl << SH1) + MSK1, (int)nn - 1));
  V = vmin_upto(V, dPos, br << SH1, (int)r);
  if (bl + 1 <= br - 1) {
    int gl = (bl + 1) >> SH1, gr = (br - 1) >> SH1;
    if (gl == gr) V = vmin_upto(V, L1D, bl + 1, br - 1);
    else {
      V = vmin_upto(V, L1D, bl + 1, min2((gl << SH1) + MSK1, (int)nb1 - 1));
      V = vmin_upto(V, L1D, gr << SH1, br - 1);
      if (gl + 1 <= gr - 1) V = vmin_upto(V, L2D, gl + 1, gr - 1);
    }
  }
  __m128i mn = _mm_min_epi32(_mm256_castsi256_si128(V), _mm256_extracti128_si256(V, 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);
  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 const KRRec *kruskal_sort(u32 m) {
  // krs[0] was filled BY THE PARSER (see solve()); nothing to copy here.
  KRRec *src = krs[0], *dst = krs[1];
  for (int pass = 0; pass < 3; pass++) {
    u32 shift = (u32)pass * RBITS;
    for (u32 j = 0; j < RSIZE; j++) cnt[j] = 0;
    for (u32 i = 0; i < m; i++) cnt[(src[i].key >> shift) & RMASK]++;
    u32 s = 0;
    for (u32 i = 0; i < RSIZE; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
    for (u32 i = 0; i < m; i++) { KRRec r = src[i]; dst[cnt[(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];
    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++) {
      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;
    {
      dial_np = 0; dial_pending = 0; dial_cur = 0; dial_mod = 0;
      for (u32 k = 0; k < DIAL_N; k++) dial_head[k] = RHNIL;
      for (u32 k = 0; k < DIAL_WORDS; k++) dial_bits[k] = 0;
      rhs_push(((u64)0u << 32) | 1u);
      while (dial_pending) {
        u64 top = rhs_pop();
        u32 d = (u32)(top >> 32), u = (u32)top;
        if (d > dist_[u]) continue;
        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 >= 8u) ? e2 - 8u : 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 + 8] & 262143u)), _MM_HINT_T0);
          if (nd < dist_[v]) {
            dist_[v] = nd;
            rhs_push(((u64)nd << 32) | v);
          }
        }
        for (; e < e2; e++) {
          u32 a = adj[e];
          u32 v = a & 262143u;
          u32 nd = d + (a >> 18);
          if (nd < dist_[v]) {
            dist_[v] = nd;
            rhs_push(((u64)nd << 32) | v);
          }
        }
      }
    }
    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++) {
        /* [n18e-A] rs[i+8].u packs (vertex | edge_length<<18): the unmasked prefetch was
           addressing dsu[] + a wild offset, i.e. it fetched nothing useful for a phase that is
           26.5% of the run and pure random-DSU latency.  Mask to the 18-bit vertex field. */
        _mm_prefetch((const char *)(dsu + (rs[i + 8].u & 262143u)), _MM_HINT_T0);
        _mm_prefetch((const char *)(dsu + rs[i + 8].v), _MM_HINT_T0);
        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;
        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);
      }
    }
    PH_MARK(5);

    g_Mn = (u64)(~0ull / (u64)n) + 1; g_Ms = (u64)(~0ull / ((u64)S + 1)) + 1;
    // ---- queries ----
    i64 lastans = 0;
    for (u32 qi = 0; qi < Q; qi++) {
      u32 v0,p0;ni_pair(v0,p0);
      u64 la = (u64)lastans;
      u32 v = (u32)fastmod((u64)(v0 - 1) + (u64)K * la, (u64)n, g_Mn) + 1;
      u32 p = (u32)fastmod((u64)p0 + (u64)K * la, (u64)S + 1, g_Ms);
      u64 vi = vinfo[v];
      u32 x = (u32)vi;
      u32 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

评测结果