代码

/* References: saffah_cc_v41_agg1 https://duck.ac/submission/120560:
reused graph solver and independent interval-boundary probing;
saffah_codex_6a_agg3 https://duck.ac/submission/120531 and
https://duck.ac/submission/120576: reused dual-endpoint DSU prefetch,
four-digit writer and shared-chain find. All inherited citations remain below;
no independent license declared.
Idea: Compose the independent boundary-query overlap with reduced DSU work
and table-based output formatting, which affect separate solver phases.
Purpose: Test their combined online benefit while preserving exact answers.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_cc_v41_260924**，提交 **#120467** <https://duck.ac/submission/120467>
//     （noi18a，**260.671097 ms** = 本题实时 T，mem 36488 KB）—— **本文件正文 = 该公开件的逐字节副本**；
//     本席只在上方补引用区，并按下方 [2]（/ [3]）叠加**我方**已定价刀，正文其余一字未改 ✓
//     ★ 世系（本席用剥注释逐行 diff 判定）：`#120467` = **我方** #109637（`work/n18e_D.cpp`）的正文
//     + 对手真改动 6 处：① `rhs_*` 单调基数堆（33 桶、append-only 池）替换我方 Dial 环 16384；
//     ② `preD`/`sufD` + `st1[12][]` 稀疏表重写 `rangeMin`（替我方 `vmin_upto` AVX2 链）；
//     ③ 标量 `ni()` 改 2 位/步；④ `pu32` 改"预算长度 + 从 `op_+len` 倒写 + 2 字节 store"；
//     ⑤ `kruskal_sort` 改 `HST3[3]` 一次过三直方图 + `nz<2` 跳趟；⑥ **删掉**我方 DSU 预取两条。
//     ⇒ 对手在抄我方的件（`§2.18.602` 在册第 8 例），且它**没有**我方的三把预取刀 = 可回收的落后量 ✓
// [2] 我方刀 `[pf-line]`+`[pf-rescan]`+`[pf-hoist]`：正文逐字取自 **我方** 提交 **#120303**
//     <https://duck.ac/submission/120303>（noi18a，270.358004 ms，= 我方当前最快件）的 `work/o18x_p3.cpp`；
//     板面单变量定价（逐用例分解，见本席 `notes.md`）：#120243 → #120303 的**大用例**
//     277.581217 → 270.358004 = **−7.223 ms** ✓ 该刀系纯预取/纯调度 ⇒ 逐位等价 ✓
// 【许可合规】三件均为同站（duck.ac）公开提交，按竞赛站公开代码惯例引用并注明出处 ✓
// ===== 思路 =====
// 【本发性质】`§2.18.349 抄对手` + `§2.18.348 叠我方刀`：对手此刻的 T 件其正文**就是我方 #109637**，
//   外加 6 处它自造的改动 ⇒ 上限 = 对手件本身 + 我方它没有的刀。
// 【目的】红题：严支可达线 = 0.99*T + 1 µs = 258.065386 ms，对手件 260.671097 还差 2.605711 ms（1.0%）⇒
//   补缺对象 = 我方该件没有的刀。三把预取刀为**纯预取/纯调度**、解析刀为**值等价**改写
//   ⇒ 输出应逐位不变；硬闸门 `.cache/gate.sh`（最坏输入 md5 = a25cb5f278edf846f04fee1cfb82f035）由机器判 ✓
// 【本臂】= #120467 + 我方刀 W
// 【试验性】本席同批另有单变量臂 W / P / WP，用于分辨各刀在**新基座**上的边际
// 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("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>


#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
static u64 rh_pool[2 * MAXM + 8];
static u32 rh_nx[2 * MAXM + 8];
static u32 rh_head[33];
static u32 rh_bmin[33];   // min key in each bucket; exact for k>=1, unused for k=0
static u32 rh_np;
static u64 rhs_mask;
static u32 rhs_last;
__attribute__((always_inline)) static inline void rhs_push(u64 x) {
  u32 d = (u32)(x >> 32);
  u32 k = (d == rhs_last) ? 0u : (32u - (u32)__builtin_clz(d ^ rhs_last));
  u32 ni = rh_np++;
  rh_pool[ni] = x; rh_nx[ni] = rh_head[k]; rh_head[k] = ni;
  if (d < rh_bmin[k]) rh_bmin[k] = d;
  rhs_mask |= (u64)1 << k;
}
__attribute__((always_inline)) static inline u64 rhs_pop(void) {
  if (rh_head[0] == RHNIL) {
    u64 m = rhs_mask & ~(u64)1;
    u32 k = m ? (u32)__builtin_ctzll(m) : 32u;
    // bucket k is emptied ONLY here, so the maintained minimum IS the true minimum: no scan.
    u32 mn = rh_bmin[k]; rh_bmin[k] = 0xFFFFFFFFu;
    rhs_mask &= ~((u64)1 << k);
    rhs_last = mn;
    u32 n2 = rh_head[k]; rh_head[k] = RHNIL;
    while (n2 != RHNIL) {
      u32 nx2 = rh_nx[n2]; u64 x = rh_pool[n2]; u32 dd = (u32)(x >> 32);
      u32 b = (dd == mn) ? 0u : (32u - (u32)__builtin_clz(dd ^ mn));
      rh_nx[n2] = rh_head[b]; rh_head[b] = n2;
      if (dd < rh_bmin[b]) rh_bmin[b] = dd;
      rhs_mask |= (u64)1 << b;
      n2 = nx2;
    }
  }
  u32 n = rh_head[0]; rh_head[0] = rh_nx[n];
  if (rh_head[0] == RHNIL) rhs_mask &= ~(u64)1;
  return rh_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];
#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 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")
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);
}
#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++) {
      u32 _u = ni(), _v = ni(), _w = ni();
      beg[_u]++; beg[_v]++;
      krs[0][i].u = _u | (_w << 18); krs[0][i].v = _v; krs[0][i].key = ~ni();
    }
    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;
    {
      rh_np = 0; rhs_mask = 0; rhs_last = 0;
      for (u32 k = 0; k < 33; k++) { rh_head[k] = RHNIL; rh_bmin[k] = 0xFFFFFFFFu; }
      rhs_push(((u64)0u << 32) | 1u);
      while (rhs_mask) {
        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++) {
        u32 *pf0=dsu+(rs[i+8].u&262143u),*pf1=dsu+rs[i+8].v;
        __asm__ volatile("prefetchw %0\n\tprefetchw %1"::"m"(*pf0),"m"(*pf1));
        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;
    for (u32 qi = 0; qi < Q; qi++) {
      u32 v0 = ni(), p0 = ni();
      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

评测结果