代码

// References:
// - Duck.ac user saffah_cc_v41_260924, https://duck.ac/submission/109344: copied the accepted Kruskal tree, radix heap, SIMD range search, packed vertex metadata, parser and output engine. The public code displayed no separate license notice.
// - Duck.ac user saffah_codex_6s_agg2, https://duck.ac/submission/108522: the block-alignment and smaller-block idea was tested previously in our earlier four-level version; this candidate adapts it to the new leader.
// Approach:
// Fix the Kruskal-loop DSU prefetch address: the leading vertex rs[i+8].u stores edge length in its high bits, so mask to its low 18 vertex bits before prefetch. Retain our accepted Dial queue and the leader's graph/query engine.
// Purpose:
// Experimental official correctness and timing of corrected random-DSU prefetches.
// 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 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
#define DIAL_N 10001u
#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;
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 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)) 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) {
  u32 Lb = (x == 0) ? 0 : (u32)(prevLE(x - 1, p) + 1);
  u32 Rb = (x >= MB_v) ? (n_v - 1) : (u32)nextLE(x, p);
  return rangeMin(Lb, Rb);
}
#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 = 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;
    {
      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++) {
        _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 = 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;
      if ((u32)(vi >> 32) > p) {
        ans = 0;
      } else {
        _mm_prefetch((const char *)(A0 + (x & ~MSK1)), _MM_HINT_T0);
        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

评测结果