代码

// References:
// - Duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/103914: copied its public graph and query solver, retaining all inherited citations. No separate license notice accompanies it.
// Approach: Retain the accepted four-level hierarchy and test compiler configuration o3 without changing graph or query logic.
// Purpose: Experimental official full-size timing and checksum comparison.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2, 提交 #103815 <https://duck.ac/submission/103815>
//     （noi18a，325.971 ms，当时本题 T）。抓取件 problems/noi18a/ref2/rival_103815.cpp。
//     用途：**直接复制了该提交的完整代码作为基底**（Kruskal 重构树、单调 radix heap、
//     AVX2 区间搜索、融合记录基数排序、输出引擎）。
// [2] duck.ac 用户 saffah_cc_v41_agg1, 提交 #103856 <https://duck.ac/submission/103856>
//     / #103882 <https://duck.ac/submission/103882> / #103896 <https://duck.ac/submission/103896>
//     用途：本工作区对 [1] 的忠实复刻、把三层分块扇出 SH1 由 5 降到 4 的一发、
//     以及给被整块扫描的表加 64 字节对齐的一发；本发在 #103896 之上只加第三层阻塞。
// [3] duck.ac 用户 saffah_cc_v41_agg1, 提交 #103778 <https://duck.ac/submission/103778>
//     用途：同一引擎的前一代；其单调 radix heap 源自 duck.ac 用户 saffah_cc_v41_260924
//     提交 #103748 <https://duck.ac/submission/103748>。
// [4] duck.ac 用户 saffah_cc_v41_260924, 提交 #86052 / #99844 / #100484 / #101111
//     <https://duck.ac/submission/86052> <https://duck.ac/submission/99844>
//     <https://duck.ac/submission/100484> <https://duck.ac/submission/101111>
//     用途：重构树 / 融合边记录排序 / 解析直接写融合记录 / Lemire fastmod 的思想，经 [3] 继承。
// 上述公开提交均未附许可声明；按本工作区惯例注明账号、原始提交地址与所用内容。
// ======================
// ===== 思路 =====
// 单变量：给已有的三层分块结构**补上第四层阻塞**，把第二层那两处 O(nb2) 的线性扫描消掉。
// 依据（本机元素流量计数器，零发数）：SH1=4 时第二层的**线性**扫描成为全场最大项 ——
//   `rm:L2Dlin` 64,019 次调用 / 1,699,496 个 SIMD 轮次 / 27,191,936 个元素（每次调用平均 27 轮）；
//   `pL2:L2Ablk` 与 `nR2:L2Ablk` 各约 833,000 轮。三者合计 **3.37 M 轮**，而其余所有扫描合计仅约 5 万轮。
// 前两层本来就是"块内 AVX2 扫描 + 跨块走上一层"，只有第二层是**从 0 一路线性扫到 g**。
// 本发按同样的形态给它加一层 L3A/L3D（扇出同样是 16，表各约 50 项 = L1 常驻）：
//   先在 g 所在的 L2 块内扫（≤16 项）；扫不到才用 L3 定位到"最近一个 min ≤ p 的 L2 块"，
//   再在该 L2 块内扫一遍。语义与前两层逐字同构，判定式完全不变。
// 预期把 3.37 M 轮降到约 0.9 M 轮。除新增两张小表与建表循环外不改任何东西。
// ================
// ===== 思路 =====
// 单变量：把三张**被整块扫描**的表按 64 字节对齐。
// 依据（本机实测，零发数）：SH1=4 时每一层的"块"恰好是 16 个 u32 = **64 字节**，
// 即一个块理应正好落在**一条 cache line** 里。但在这份源码里这些表只被 gcc 对齐到 32 字节
// （实测 `A0%64=0` 但 `dPos%64=32`、`L1A%64=32`、`L1D%64=32`、`L2A%64=32`、`L2D%64=32`）
// ⇒ **每个 64 字节的块都横跨两条 cache line** ⇒ 每次块扫描的 line 流量翻倍。
// dPos 是 800 KB 的随机访问表，L1A/L1D 各 50 KB，L2A/L2D 各约 3 KB；
// 而"每次块扫描少碰一条 line"正是 SH1 6->5（-2.47%）与 5->4（-1.95%）两次兑现的**同一个机理**。
// 本发只给 `A0/dPos/L1A/L1D/L2A/L2D` 加 `__attribute__((aligned(64)))`，不改任何其它东西。
// ================
// ===== 思路 =====

// 单变量：把三层分块结构的扇出常数从 SH1=5（块 32）再降到 **SH1=4（块 16）**。
// 机理（与对手 #103815 那次 SH1 6->5 同一条）：A0 与 dPos 各 800 KB，在判题机 256 KB L2 上
// 是随机访问；一次 `scanLeftLE(A0, i0 & ~MSK1, i0, p)` 触到的 cache line 数 ≈ ceil(块内跨度/16)。
// 块 32 时最多 2 条线，块 16 时最多 1 条 ⇒ A0/dPos 的 line 流量减半。
// 代价：L2A/L2D 这两张**极小**（块 16 时 L2A/L2D 各约 (n/256) 项 ≈ 780 项 = 3 KB，L1 常驻）
// 的线性扫描会变长，属 uop 级开销。
// 本发只改常数，算法/数据结构逐字节不变。

// ================
// ===== 思路 =====
// 本发 = **把基底换成对手当前榜首 #103815 的忠实复刻**（BRIEF §2.16 的标准 heal 流程）。
// #103815 相对我们 #103778 的全部正文差异只有 5 行：
//   * `#define PHASE_TIMING 1` 删除（判题构建里它只做 8 次 rdtsc + 一次 fprintf(stderr)，
//     但对手明确移除；顺带让本地 profile 版与提交版分离）；
//   * 三层分块的扇出 SH1 由 6 改成 5（MSK1 63→31，MAXB1/MAXB2 的除数 64→32）
//     ⇒ A0/L1A 的一级块扫描从 ≤64 个元素降到 ≤32 个（AVX2 一轮 16 个元素）
//     代价是 L2A/L2D 的线性扫描从 ≤49 升到 ≤196 个元素。对手实测整族净值 -8.25 ms。
// 本发不改任何其他东西：先把这一代引擎作为新基线落地，后续每一发都在它上面做单变量。
// ================
// References:
// [0] saffah_codex_6s_agg2, duck.ac submission #103804,
//     https://duck.ac/submission/103804 . Directly copied its accepted
//     Kruskal tree, radix heap, AVX2 interval search and output engine.
// [1] saffah_cc_v41_agg1, duck.ac submission #103778,
//     https://duck.ac/submission/103778 . Complete engine inherited via [0].
// [2] saffah_cc_v41_260924, duck.ac submission #103748,
//     https://duck.ac/submission/103748 . Monotone radix heap copied
//     into [1], inherited here.
// [3] saffah_cc_v41_260924, duck.ac submissions #86052, #99844,
//     #100484, #101111: https://duck.ac/submission/86052,
//     https://duck.ac/submission/99844,
//     https://duck.ac/submission/100484,
//     https://duck.ac/submission/101111 . Reconstruction tree,
//     fused edge sorting and fastmod ideas inherited through [1].
// No separate license notices appeared on these public submissions;
// authors, URLs and reused components are credited here.
// Approach:
// Use 32-element instead of 64-element blocks in the AVX2 boundary
// searches and range minimum hierarchy. This cuts first-level scans
// approximately in half while keeping the same three-level structure.
// Purpose:
// Measure the altered query/block balance on the official judge and
// determine whether it reaches the exact current noi18a target.
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#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>
// PHASE_TIMING intentionally undefined: no per-phase rdtsc or stderr trace.

#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 4
#define MSK1 15
#define MAXB1 (MAXN / 16 + 2)
#define MAXB2 (MAXB1 / 16 + 2)
#define MAXB3 (MAXB2 / 16 + 2)

static u32 eln[MAXM];
struct KRRec { u32 key; u32 u; u32 v; };   /* key = ~alt : descending altitude */
static KRRec krs[2][MAXM];
static u32 beg[MAXN + 2], curs[MAXN + 2], cnt[RSIZE + 1];
static u32 adj[MAXARC];
static u32 sz[MAXND];
static u32 zeroAlt[MAXN];
static u32 dist_[MAXN + 2];
// ---- MONOTONE RADIX HEAP (ported from duck.ac #103748, saffah_cc_v41_260924) ----
// 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_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;
  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;
    u32 ni = rh_head[k], mn = (u32)(rh_pool[ni] >> 32);
    for (u32 t = rh_nx[ni]; t != RHNIL; t = rh_nx[t]) {
      u32 dd = (u32)(rh_pool[t] >> 32); if (dd < mn) mn = dd;
    }
    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;
      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];
static u32 posOf[MAXN + 2];
static u32 dPos[MAXN] __attribute__((aligned(64)));
static u32 A0[MAXN] __attribute__((aligned(64)));
static u32 L1A[MAXB1] __attribute__((aligned(64))), L2A[MAXB2] __attribute__((aligned(64)));
static u32 L1D[MAXB1] __attribute__((aligned(64))), L2D[MAXB2] __attribute__((aligned(64)));
static u32 L3A[MAXB3] __attribute__((aligned(64))), L3D[MAXB3] __attribute__((aligned(64)));
static u32 MB, nb1, nb2, nb3, nn;

#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_;
  while (*p <= ' ') p++;
  u32 v = (u32)(*p++ - '0');
  while (*p > ' ') v = v * 10 + (u32)(*p++ - '0');
  ip_ = p;
  return v;
}

static const char D2[] =
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899";

// Bulk-digit output: digits are built right-aligned in t[] and copied out with one
// (or two, for >=9 digits) 8-byte stores that together cover exactly [op_, op_+len).
// A one-byte store adds the newline.  Callers only take this path while
// op_+16 <= oendv so the store never leaves the stdout buffer.
static u64 oendv = ~0ULL;
static inline void pu32(u32 v) {
  char t[32];
  char *p = t + 24;
  while (v >= 100) {
    u32 d = v / 100, r = (v - d * 100) * 2;
    v = d;
    *--p = D2[r + 1]; *--p = D2[r];
  }
  if (v >= 10) { u32 r = v * 2; *--p = D2[r + 1]; *--p = D2[r]; }
  else *--p = (char)('0' + v);
  u32 len = (u32)(t + 24 - p);
  char *o = op_;
  u64 c0;
  __builtin_memcpy(&c0, p, 8);
  __builtin_memcpy(o, &c0, 8);
  if (len > 8) {
    u64 c1;
    __builtin_memcpy(&c1, p + (len - 8), 8);
    __builtin_memcpy(o + (len - 8), &c1, 8);
  }
  o[len] = '\n';
  op_ = o + len + 1;
}
// conservative byte-at-a-time path, used only for the very last number
static inline void pu32_safe(u32 v) {
  char t[12]; int q = 0;
  if (!v) t[q++] = '0';
  while (v) { t[q++] = (char)('0' + v % 10); v /= 10; }
  while (q) *op_++ = t[--q];
  *op_++ = '\n';
}
// ---- SIMD (AVX2) scans ----
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 - 15 >= lo) {
    __m256i x0 = _mm256_loadu_si256((const __m256i *)(arr + j - 15));
    __m256i x1 = _mm256_loadu_si256((const __m256i *)(arr + j - 7));
    u32 b0 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x0, vp)));
    u32 b1 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x1, vp)));
    u32 bits = (~(b0 | (b1 << 8))) & 0xFFFFu;
    if (bits) return j - 15 + (31 - __builtin_clz(bits));
    j -= 16;
  }
  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 + 15 <= hi) {
    __m256i x0 = _mm256_loadu_si256((const __m256i *)(arr + j));
    __m256i x1 = _mm256_loadu_si256((const __m256i *)(arr + j + 8));
    u32 b0 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x0, vp)));
    u32 b1 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x1, vp)));
    u32 bits = (~(b0 | (b1 << 8))) & 0xFFFFu;
    if (bits) return j + __builtin_ctz(bits);
    j += 16;
  }
  for (; j <= hi; j++) if (arr[j] <= p) return j;
  return hi + 1;
}
static inline u32 scanMin(const u32 *arr, int lo, int hi) {
  u32 m = 0xFFFFFFFFu;
  int j = lo;
  while (j + 15 <= hi) {
    __m256i x0 = _mm256_loadu_si256((const __m256i *)(arr + j));
    __m256i x1 = _mm256_loadu_si256((const __m256i *)(arr + j + 8));
    __m256i mm = _mm256_min_epu32(x0, x1);
    mm = _mm256_min_epu32(mm, _mm256_permute2x128_si256(mm, mm, 0x01));
    mm = _mm256_min_epu32(mm, _mm256_shuffle_epi32(mm, 0x4E));
    mm = _mm256_min_epu32(mm, _mm256_shuffle_epi32(mm, 0xB1));
    u32 t = (u32)_mm_cvtsi128_si32(_mm256_castsi256_si128(mm));
    if (t < m) m = t;
    j += 16;
  }
  for (; j <= hi; j++) if (arr[j] < m) m = arr[j];
  return m;
}
static inline int min2(int a, int b) { return a < b ? a : b; }

// nearest b <= i with A0[b] <= p (or -1);  i <= MB-1
__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, g & ~MSK1, g, p);
  if (r < 0) {
    int h = (g >> SH1) - 1;
    if (h < 0) return -1;
    r = scanLeftLE(L3A, 0, h, p);
    if (r < 0) return -1;
    r = scanLeftLE(L2A, r << SH1, min2((r << SH1) + MSK1, (int)nb2 - 1), 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);
}
// nearest b >= i with A0[b] <= p (or MB);  i <= MB-1
__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;
  int ge = min2((g & ~MSK1) + MSK1, (int)nb2 - 1);
  r = scanRightLE(L2A, g, ge, p);
  if (r > ge) {
    int h = (g >> SH1) + 1;
    if (h >= (int)nb3) return (int)MB;
    r = scanRightLE(L3A, h, (int)nb3 - 1, p);
    if (r > (int)nb3 - 1) return (int)MB;
    r = scanRightLE(L2A, r << SH1, min2((r << SH1) + MSK1, (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) {
  int bl = (int)(l >> SH1), br = (int)(r >> SH1);
  if (bl == br) return scanMin(dPos, (int)l, (int)r);
  u32 m = scanMin(dPos, (int)l, min2((bl << SH1) + MSK1, (int)nn - 1));
  u32 t = scanMin(dPos, br << SH1, (int)r);
  if (t < m) m = t;
  if (bl + 1 > br - 1) return m;
  int gl = (bl + 1) >> SH1, gr = (br - 1) >> SH1;
  if (gl == gr) { t = scanMin(L1D, bl + 1, br - 1); if (t < m) m = t; return m; }
  t = scanMin(L1D, bl + 1, min2((gl << SH1) + MSK1, (int)nb1 - 1)); if (t < m) m = t;
  t = scanMin(L1D, gr << SH1, br - 1); if (t < m) m = t;
  if (gl + 1 <= gr - 1) {
    int fl = gl + 1, fr = gr - 1, hl = fl >> SH1, hr = fr >> SH1;
    if (hl == hr) { t = scanMin(L2D, fl, fr); if (t < m) m = t; }
    else {
      t = scanMin(L2D, fl, min2((hl << SH1) + MSK1, fr)); if (t < m) m = t;
      t = scanMin(L2D, hr << SH1, fr); if (t < m) m = t;
      if (hl + 1 <= hr - 1) { t = scanMin(L3D, hl + 1, hr - 1); if (t < m) m = t; }
    }
  }
  return m;
}

// radix sort of FUSED edge records: every access is sequential.  Sorting indices made each
// pass chase eal[src[i]] / eu[e] / ev[e] at random.
static const KRRec *kruskal_sort(u32 m) {
  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;
}

static void solve() {
  u32 T = ni();
  while (T--) {
    PH_START();
    u32 n = ni(), m = ni();
    // parse STRAIGHT into the fused record: eu/ev/eal exist for nothing else, so writing them
    // first costs a full 12 B/record write plus a 12 B/record read and a whole array set.
    for (u32 i = 0; i < m; i++) { krs[0][i].u = ni(); krs[0][i].v = ni(); eln[i] = ni(); krs[0][i].key = ~ni(); }
    u32 Q = ni(), K = ni(), S = ni();
    PH_MARK(0);

    // ---- CSR ----
    for (u32 i = 1; i <= n; i++) beg[i] = 0;
    for (u32 i = 0; i < m; i++) { beg[krs[0][i].u]++; beg[krs[0][i].v]++; }
    {
      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, b = krs[0][i].v, w = eln[i];
        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;
      rhs_push(((u64)0u << 32) | 1u);
      while (rhs_mask) {
        u64 top = rhs_pop();
        u32 d = (u32)(top >> 32), u = (u32)top;
        {
          u32 i = 0;
        }
        if (d > dist_[u]) continue;
        u32 e = beg[u], e2 = beg[u + 1];
        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);
      for (u32 i = 0; i < m; i++) {
        u32 a = find_(rs[i].u), b = find_(rs[i].v);
        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 sp = 0;
      stk[sp++] = N;
      u32 c = 0;
      while (sp) {
        u32 u = stk[--sp];
        if (u <= n) {
          posOf[u] = c;
          dPos[c] = dist_[u];
          Rr[u] = c;
          c++;
        } else {
          stk[sp++] = ch2[u]; stk[sp++] = ch1[u];
        }
      }
    }
    for (u32 u = 1; u <= n; u++) sz[u] = 1;
    for (u32 u = n + 1; u <= N; u++) {
      sz[u] = sz[ch1[u]] + sz[ch2[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
    {
      for (u32 i = 0; i < n; i++) zeroAlt[i] = 0xFFFFFFFFu;
      u32 pos1 = posOf[1];
      u32 u = N;
      while (u > n) {
        u32 c1 = ch1[u], c2 = ch2[u];
        if (pos1 <= Rr[c1]) {
          u32 hi = Rr[c2], lo = hi - sz[c2] + 1;
          for (u32 i = lo; i <= hi; i++) zeroAlt[i] = alt_[u];
          u = c1;
        } else {
          u32 hi = Rr[c1], lo = hi - sz[c1] + 1;
          for (u32 i = lo; i <= hi; i++) zeroAlt[i] = alt_[u];
          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);
      }
      nb3 = (nb2 + MSK1) >> SH1;
      for (u32 j = 0; j < nb3; j++) {
        u32 lo = j << SH1, hi = lo + MSK1;
        if (hi >= nb2) hi = nb2 - 1;
        L3A[j] = scanMin(L2A, (int)lo, (int)hi);
        L3D[j] = scanMin(L2D, (int)lo, (int)hi);
      }
    }
    PH_MARK(5);

    // ---- queries ----
    i64 lastans = 0;
    u64 Mn = 0xFFFFFFFFFFFFFFFFULL / (u64)n;
    u64 Ms = 0xFFFFFFFFFFFFFFFFULL / ((u64)S + 1);
    for (u32 qi = 0; qi < Q; qi++) {
      u32 v0 = ni(), p0 = ni();
      u64 la = (u64)lastans;
      u32 v, p;
      if (K) {
        u64 xv = (u64)(v0 - 1) + la;
        u64 xp = (u64)p0 + la;
        u64 qv = (u64)(((__uint128_t)xv * Mn) >> 64);
        u64 rv = xv - qv * (u64)n; if (rv >= (u64)n) rv -= (u64)n;
        u64 qp = (u64)(((__uint128_t)xp * Ms) >> 64);
        u64 rp = xp - qp * ((u64)S + 1); if (rp >= (u64)S + 1) rp -= (u64)S + 1;
        v = (u32)rv + 1; p = (u32)rp;
      } else { v = v0; p = p0; }
      u32 x = posOf[v];
      u32 ans;
      if (zeroAlt[x] > p) {
        ans = 0;
      } else {
        _mm_prefetch((const char *)(A0 + (x & ~MSK1)), _MM_HINT_T0);
        u32 Lb = (x == 0) ? 0 : (u32)(prevLE(x - 1, p) + 1);
        u32 Rb = (x >= MB) ? (n - 1) : (u32)nextLE(x, p);
        ans = rangeMin(Lb, Rb);
      }
      lastans = (i64)ans;
      if ((u64)op_ + 16 <= oendv) pu32(ans); else pu32_safe(ans);
    }
    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;
  oendv = (u64)g_out + sizeof(g_out) - 32;
  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;
    oendv = (u64)D->o + (D->ol > 32 ? D->ol - 32 : 0);
    solve();
    D->os = (u64)(op_ - D->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
#endif

评测结果