代码

/* References: saffah_cc_v41_agg1 https://duck.ac/submission/120430 and
saffah_codex_6a_agg3 https://duck.ac/submission/120714: inherited suffix
automata and vector input scanning. All earlier source citations remain
below; no independent license declared.
Idea: If a state's latest end position equals its maximum substring length,
it has exactly one end position: no occurrence can end before that length.
When that position exceeds the query's right boundary, its active maximum
is therefore zero without an Euler interval query.
Purpose: Avoid random range-maximum work for the many unique prefix states.
*/
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/120430 and
saffah_codex_6a_agg3 https://duck.ac/submission/120622: inherited suffix
automata and fresh-row clearing elimination. All earlier credits retained
below; no independent license declared.
Idea: Locate each lowercase input string's end32 bytes at a time using one
SIMD delimiter mask, with a bounded scalar tail.
Purpose: Avoid scanning the source and query strings one character at a time
before the automata perform their actual processing.
*/
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/120430:
reused suffix automata and all query logic. Earlier citations remain below;
no independent license declared.
Idea: A transition row used for the first time is already zero in BSS. Track
the highest allocated query-SAM row and omit its redundant initial clearing;
clone allocation also advances this frontier. Reused rows are still cleared.
Purpose: Eliminate80 bytes of stores for each newly reached automaton state
without relying on query contents or changing the matching algorithm.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #120368 <https://duck.ac/submission/120368>
//     用途：**本文件正文的直接父件**（本席入场时榜首 T = 132.755591 ms）。本席对其做逐 token
//     diff（去掉注释后与本站 #107930 正文比较）⇒ #120368 正文 **= 本账号 #107930 的逐字节副本**
//     （提取出的正文 md5 04a9b5022107ca4a591989136be6003d，本席复制的版本与之逐位相同），
//     只在匹配回路里做了 3 行"过渡前瞻"改写：`int nx=sget(v,c); int vn=s_link[v];` 提到字符循环
//     开头、回退环改成 `while(v!=1 && !nx){...}` 复用 nx、并消掉回退环尾那次 sget。
//     ⇒ 属 `§2.18.349` 的"对手抄我方最新件"型：**抄件上限 = 对手件本身 = 132.756 ms，仍高于严支
//     131.429035 ms ⇒ 纯抄不可能达标**，故本发 = 抄下它 + 本席自己的一刀（见 思路）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107930 <https://duck.ac/submission/107930>
//     用途：间接父件 / 本文件正文的血缘（s_nxt 20 位打包 · t_nxt 3 字节打包 · 计数排序代替桶链表 ·
//     回退链链接前瞻）。其自带的 REFERENCES / 思路 两块**原样保留**在下方（引用链完整可溯）。
// [3] `problems/noi18c/notes.md`（第四轮相位账 + `e18d_` 席结论）用途：tc17 = 解析+SAM(S) 35.28 ms |
//     build_ord+meta 4.00 | **匹配 f[] 85.63 ms（61%）** | SAM(T)+累加 13.78 | emit 0.54；
//     以及"本族对地址足迹/访存条数敏感、对步长放大极敏感"的既有结论。本发打的正是那 61%。
// 许可证：以上均为 duck.ac 公开提交与公开题面，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径（`python3 tools/exact.py noi18c`，判题机原值）】
//   mine = **134.197040**（#107930）· T = **132.755591**（#120368 saffah_codex_6a_agg3）
//   ⇒ 宽支 1.005*T+1µs = 133.420369（现实差 0.776671 ms）；**任何新最好件一律翻严支**
//     ⇒ 真栏 = **0.99*T+1µs = 131.429035**，**差 2.768005 ms（2.063%）**。
//
// 【本发 = #120368 正文 + 一件（ARM FULLRANGE：整区间询问裁掉见证/裁剪机制）】
//   * 本席先在**本机对 tc17 形状**（|S|=5e5 随机 26 字母，单询问 |T|=1e6，l=1 r=|S|）打点实测：
//       fast（见证快路）= **38,424 / 1,000,000 字符 = 3.8%**；slow = 961,576；回退环总级数
//       984,699 ⇒ **1.024 级/次**；**clip 迭代 = 961,576 = 恰好 1 次/次慢路** ⇒ clip 在该形状上
//       **只执行首轮就 break**（`lim = mxo[v] - l0 >= len` 恒真）。
//   * ⇒ 在这类询问上，"见证 e + fast path + clip"三件套**每字符要付 ~1.9 次随机取数**
//     （clip 的 `mxo[v]` 一次 + 每次 fast 判定的 `sstart[e+1]` 一次），却只换来 3.8% 的
//     "省掉一次 0 级回退"——回退本身在该形状平均只有 1.024 级。
//   * 改法（**两处，均为语义等价化简，不是近似**）：
//       (a) `l0==0 && q.r>=sn`（整区间）时走专用回路：只做"回退环 + 过渡"，不做 fast path、不做 clip；
//       (b) 专用回路里的 f_[i] 与通用回路**逐位相同**：fast path 命中时必有 `sget(v,c)!=0`
//           （否则"见证延长"就不是 S 中的一次出现），故通用回退环在**第 0 级**就退出，
//           得到同一个 (v, len)；clip 在整区间上不改 len（证明见代码内注释）。
//   * 为什么值得：tc17 属 `r >= |S|` 家族（notes.md 相位账：惰性 Euler + 激活合计仅 1.33 ms、
//     `qmax/tin/tout` 全程未被触碰；本席本地打点亦证实 clip 从不改 len），**整区间 = 主战场**。
//   * **正确性闸门**：本机 93 组语料（`/home/yjp/duck.ac/.cache/n1b/cv/`，覆盖 eul_ready=0/1、
//     2/4/7/26 字母、周期串、`:full`/`:rand`、|S|=500000 三组大测）与本账号 #107930 正文
//     **输出逐字节相同（93/93）**；新回路只对 `l==1 && r>=|S|` 的询问生效，其余询问走原路一字未动。
//   * **本地定价（交错配对，min-of-7）**：tc17 形状上 parent 533 / 565 ms（min/中位）→ 本件
//     513 / 542 ms ⇒ **约 -3.8% ~ -4.1%**。判题机值以正式提交为准。
// ======================
/* References:
[1] saffah_cc_v41_agg1, https://duck.ac/submission/107930.
Reused the suffix-automaton and interval-query implementation, retaining its
inherited citations below. No separate public-source license is declared.
Idea: Fetch the next transition before testing the witness fast path, carry that
transition through suffix-link fallback, and reuse the terminating lookup.
This removes duplicate loads and exposes independent link/transition accesses.
Purpose: Measure a shorter dependency chain in the dominant matching loop.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_260924，提交 #107908
//     <https://duck.ac/submission/107908>  用途：**当前榜首 T = 137.375591 ms**，也是本发这把刀的
//     **形态出处**。本席把 `ref2/rival_107908.cpp` 与本站 #104213 正文做了逐 token（去注释行）diff：
//     两边是**不同血缘**（对手用 `u32 s_nxt[26/state]` 稠密表 + `#pragma GCC optimize("O3")` +
//     `TM[]` u64 打包；本站用 20 位打包的 65 B 行 + 惰性 Euler），但在**回退链**这一处，对手的写法明显更好：
//         ours : `while(v!=1 && !sget(v,c)) v = s_link[v];`        （每级才去取下一级链接）
//         rival: `int vn = s_link[v]; while(v!=1 && !(nx=sget(v,c))){ v=vn; len=s_len[v]; vn=s_link[v]; }`
//     ⇒ 对手把**下一级的 `s_link` 提前到本级测试之前**取，两条载入彼此独立；本站的写法让每级的
//       `s_link` 载入卡在上一级的链上。本发即把这一条**字面移植**过来（只移植"前瞻"这一件事，
//       不搬对手的 `u32` 稠密表、不搬 `O3`、不搬 `TM[]`）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104213
//     <https://duck.ac/submission/104213>  用途：本文件正文的**直接父件**（tc17 = 138.447 ms）。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #103996
//     <https://duck.ac/submission/103996>  用途：间接父件（`s_nxt` 20 位打包 + 计数排序）。
// [4] `problems/noi18c/notes.md` 第四轮相位账：tc17 = 解析+SAM(S) 35.28 ms | build_ord+meta 4.00 |
//     **匹配 f[] 85.63（61%）** | SAM(T)+累加 13.78 | emit 0.54 ⇒ 本发打的正是那 61%。
// 许可证：以上均为 duck.ac 公开提交与公开题面，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径（`python3 tools/exact.py noi18c`）】
//   mine = **138.446515**（#104213）· T = **137.375591**（#107908，saffah_cc_v41_260924）
//   ⇒ 宽支 1.005*T+1us = 138.063469（现实差 0.383046 ms）；**新最好件一律翻严支**
//     ⇒ 真正的栏是 **0.99*T+1us = 136.002835**，**差 2.443680 ms（1.765%）**。
//
// 【本发 = #104213 正文 + 一件（单变量，5 行）—— ARM LNKLA：回退链的链接前瞻】
//   * 站点：占 tc17 **61%（85.63 ms）** 的匹配回路里的后缀链接回退
//     `{ int ov=v; while(v!=1 && !sget(v,c)) v=(int)s_link[v]; if(v!=ov) len=(int)s_len[v]; }`
//   * 改法：把 `int vn = (int)s_link[v];` 提到循环之前，循环体变成 `{ v = vn; vn = (int)s_link[v]; }`
//     ⇒ 本级"测 sget"与"取下一级链接"变成**两条独立载入**，指针追逐的链不再串行
//       （形态逐字取自对手 #107908；`len` 仍保持本站"只在停下的那一级读一次"的更优写法）。
//   * 为什么这条才值得移植：本站与对手在**表布局**上的选择相反（本站 65 B/行打包，对手 104 B/行稠密），
//     而本 lane 已实证"缩足迹类改动必须用正式提交定价、probe 1/5 规模不迁移"；但**回退链的前瞻
//     与表大小无关**，是纯代码形状，因此可以安全地单独移植并单独定价。
//   * 安全性：`s_link[1] == 0`，故 `v==1` 时循环条件先短路、`vn` 永不被使用；语义与父件逐位相同
//     （本机 93 组语料逐字节对拍，含 |S|=500000 的三组大测，**93/93 相同**）。
//
// 【本席先做的两件测量/否证（本发的前置）】
//   * **harness 常数 = 0.002375 ms**（空体诊断件 #107924：`run()` 体清空 ⇒ WA、Time 由判题机照报）。
//     ⇒ noi18c 落在 `§2.19.840` 六测点分布的 **≈0% 那一端**（不是 wc2017b2 的 26%）：
//       **缺口 2.443680 ms 是 100% 真 work，没有任何"按 measured−harness 重算"能把它变小。**
//   * **上一轮备着的 `n1b_msk.cpp`（26 位转移掩码）判题机实测为负**：提交 **#107919 = 146.329 ms**
//     （父件 138.447）⇒ **+7.88 ms**，且 25 个测试点**全部**变慢、每点活跃内存 +2.5 MB。
//     ⇒ 该刀"环内每级 ~100 周期是页行走"的前提在判题机尺度**不成立**（回退链比它假设的短），
//       而多出来的一张表反而要付 TLB/页代价。**轴关闭，不要再试。**
//
// 【正确性闸门】
//   * 本机 93 组语料（`/home/yjp/duck.ac/.cache/n1b/cv/`，覆盖 eul_ready=0/1、2/4/7/26 字母、
//     周期串、`:full`/`:rand`、三个 |S|=500000 大测）与父件**输出逐字节相同**。
//   * `g++ -O2 -std=c++11` 本地编译 rc=0；`e18d_bl` 逐组 rc=0。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #103842 <https://duck.ac/submission/103842>
//     （本题当前榜首）用途：**直接复制**了对方相对我们 #99767 的两处改动，逐字节复刻：
//     (a) SAM(T) 的转移表 t_nxt 也做 3 字节打包：`u32 t_nxt[(2*MAXT+8)*26]` ->
//         `u8 t_nxt[(2*MAXT+10)*80] __attribute__((aligned(16)))`；tget/tset 改成 3 字节偏移上的
//         4 字节 load + `&0xFFFFFF` / 4 字节读-改-写（保留高字节）；tzero 由 3 条 32B + 1 条 16B
//         store（104 B）改成 5 条对齐 16B store（80 B）；clone 的 memcpy 由 104 B 变 80 B。
//     (b) 区间最大值的块长 `EBS 32 -> 8`（`EBSH 5 -> 3`）。
//     本地归档：problems/noi18c/ref2/rival_103842.cpp
// [2] duck.ac 用户 saffah_cc_v41_260924，提交 #99767 <https://duck.ac/submission/99767>
//     用途：直接复制了本文件的原型（我们自己的最好件 problems/noi18c/work/nc_sn3.cpp）。
// [3] duck.ac 用户 saffah_cc_v41_260924，提交 #87737 <https://duck.ac/submission/87737>
//     用途：直接复制了本题的全部算法与代码骨架（SAM(S)/SAM(T)、后缀链接树 Euler 区间、
//     按 r 单调激活、区间最大值查询流程、输入解析与输出格式）。
// [4] duck.ac 用户 saffah_cc_v41_260924，提交 #99553 <https://duck.ac/submission/99553>
//     用途：**参考了思想**（不是复制代码）——「纯分块扫描 + 两级块和」的区间最大值结构
//     （eactivate 只写 ev/ebmax/eb2 三个位置、qmax 用 32B 单条取数 + 重叠尾块取数）。
// [5] duck.ac 用户 saffah_cc_v41_260924，提交 #99482 <https://duck.ac/submission/99482>
//     用途：**参考了思想** —— Euler 区间惰性构造（只算 mxo[]，区间/tin/tout 延迟到第一次
//     真的需要区间最大值时才做）。
// 以上均为公开提交，未见附带的许可证声明；此处按「作者账号 + 原始提交地址 + 所用内容」逐条注明。
// ======================
// ===== 思路 =====
// 【1】复刻 REFERENCES [1]（这一步把对方相对我们 #99767 的两处差距归零）。
//
// 【2】s_nxt 由 3 字节/项（78 B/行）压到 **20 位/项（65 B/行）**，行宽 -17%。
//   状态号 <= 2*MAXS+8 = 1000018 < 2^20 ⇒ 20 位无损（严格小于 2^20 = 1048576，余量 4.6%）。
//   项 c 落在行内第 20c 位；(20c)&7 = 4*(c&1) 恒为 0 或 4，所以只要在字节偏移
//   floor(20c/8) = (5c)>>1 处做一次 **4 字节** load 就一定能取到整项（20+4 = 24 <= 32）：
//     取值 = (u32 load >> ((c&1)<<2)) & 0xFFFFF；
//     存值 = 同一处的 4 字节读-改-写（掩掉 20 位、其余原样写回 ⇒ 不污染邻居项/相邻行）。
//   行宽 65 是奇数 ⇒ 相邻行的 4KB 页内相位逐行平移 1（顺带破 4KB 同余，BRIEF §2.18.323）。
//   本方向（**只做更小更紧凑**）是本族唯一被反复验证的正面方向：
//   104B -> 78B（我们 #99767，-4.59 ms），而两次"加大足迹"（16B 结构体打包、8B 字段合并）
//   分别实测 2.1x 更差 / +4~6%。本次是同一个方向的继续。
//
// 【3】build_meta 的「按 len 分桶链表」换成 **计数排序**（去掉串行指针追逐）。
//   * SAM 构造时把 `bnext[cur]=bhead[L]; bhead[L]=cur;`（一次随机写）改成 `bhead[len]++`
//     （递增写，几乎顺序）；**整个 bnext[] 数组（s_sz*4 B）不再存在、不再被触碰**。
//   * 走一遍计数排序把状态按 len 升序摊进 ord_[]（散列那趟是 2 次无链式依赖的 RMW，
//     MLP 好），于是自底向上那趟不再有 `v = bnext[v]` 这条每状态一次随机访存的**串行链**。
//   * ord_ 现在是 **len 升序**，所以 build_meta（自底向上）改为**逆序**扫；
//     build_intervals 的两趟随之对调（正序 = 父先 = 前序编号；逆序 = 子先 = 子树大小）。
//
// 【判定机上的实测量（tools/probe.py 立即体验，真实评测机，同一驱动同一输入）】
// 三个尺度、每格都是判题机 wall time / run 内 rdtsc 相位周期：
//   scale            #99767 血统(3B,链)   本件(20bit+计数排序)
//   sz=121437        5.010 ms / 17.94 Mc   4.725 ms / 16.91 Mc   (-5.7%)
//   sz=187969 (2字母) 7.506 ms / 26.92 Mc   6.808 ms / 24.41 Mc   (-9.3%)
//   sz= 66682        5.453 ms / 19.53 Mc   5.310 ms / 19.01 Mc   (-2.6%)
//   相位：sam 14913930 -> 13826264 (-7.3%)、22131992 -> 20025232 (-9.5%)；
//         meta 4597358 -> 4188058 (-8.9%，2 字母大 clone 档)；match/samt 基本不变。
// 本次为正式提交：直接冲击达标线。
// ================
// NOI2018 你的名字  --  JudgeDuck (MAIN style)

#include <string.h>
#include <stdint.h>
#include <immintrin.h>

#pragma GCC push_options
#pragma GCC target("avx2,popcnt,bmi,bmi2")

typedef unsigned char u8;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long ul;

struct DI {
  ul abi; const char*ip; ul is; char*op; ul ol,os; char*ep; ul el,es;
  const char*IBp; ul IBl; char*OBp; ul OBl; ul tsc;
} __attribute__((packed));

#define MAXS 500005
#define MAXST 1000016
#define MAXQ 100005
#define MAXT 1000008
#define MAXTT 2000016

static u32 bhead[MAXS+8], szsub[MAXST], nxt[MAXST];   // bhead = len histogram -> start offsets
static u32 tin[MAXST], tout[MAXST], mxo[MAXST];
static u32 ord_[MAXST]; static int nord_;   // len-descending state order (lazy-Euler)
static int eul_ready;
// ancestor painting (see 思路): wl_last[x] = max own+1 among activated prefix-states
// whose suffix-link path passes through x  ==  MX(x, r) exactly.
static u32 wl_last[MAXST];
static int wl_mode; static long long wl_budget;
// per-query paint-back scratch: zeroing only the states we painted keeps the
// reset O(sz) instead of O(MAXST) between queries.
static u32 plist_[MAXST];

// ======================= SAM of S (dense 26-way transitions) ==============
// transitions of state p are at s_nxt[p*26 .. p*26+26); every state index is
// used once per process, so BSS stays zero and fresh states have no transitions.
// Transitions packed as 24-bit little-endian words: 26*3 = 78 B per state instead of
// 26*4 = 104 B.  State ids are <= 2*MAXS+8 < 2^24, so 24 bits are lossless.
// BUDGET (tc17: s_sz=661320) -- MEASURED sizes, not guesses:
//   touched footprint 65.6 MB -> 49.2 MB (-16.4 MB) = -4197 first-touch pages.
//   At the measured 244 ns/page that alone is -1.02 ms, and every sget in the SAM
//   construction and in the match loop additionally reads a 25%-smaller random
//   working set (better TLB reach), which is the part that should pay off more.
// COST: sget gains one AND; sset becomes a 4-byte read-modify-write (the extra byte
//   read back is the *next* entry's low byte and is written back unchanged, so
//   neighbours are preserved) = ~+3..5 uops per access.  Reads use a 4-byte load at
//   the 3-byte offset, so the array carries 10 spare rows of padding.
/* --- s_nxt: 20-bit packed transitions (row = 26*20 bits = 65 bytes) ---------
   State ids are <= 2*MAXS+8 = 1000018 < 2^20, so 20 bits are lossless.
   Row stride 65 B instead of 78 B (-17% footprint on the dominant table).
   Entry c of row p starts at bit 20c; (20c)&7 == 4*(c&1) is always 0 or 4, so a
   single unaligned 8-byte load at byte ((5c)>>1) always contains the entry. */
static u8 s_nxt[(2*MAXS+10)*65 + 16];
static u32 s_len[MAXST], s_link[MAXST];
static int s_sz, s_last;
static u32 s_own[MAXS];
#define S20_MASK 0xFFFFFu
static inline int sget(int p, int c){
  size_t off = (size_t)p*65 + (size_t)(((unsigned)c*5u)>>1);
  u32 x; __builtin_memcpy(&x, s_nxt + off, 4);
  return (int)((x >> (((unsigned)c&1u)<<2)) & S20_MASK);
}
static inline void sset(int p, int c, int t){
  size_t off = (size_t)p*65 + (size_t)(((unsigned)c*5u)>>1);
  u32 x; __builtin_memcpy(&x, s_nxt + off, 4);
  unsigned sh = ((unsigned)c&1u)<<2;
  x = (x & ~(S20_MASK << sh)) | (((u32)t & S20_MASK) << sh);
  __builtin_memcpy(s_nxt + off, &x, 4);
}
static void build_sam_s(const char* S, int n){
  s_sz = 1; s_last = 1;
  s_len[1] = 0; s_link[1] = 0;
  memset(bhead, 0, (size_t)(n+2)*4);
  for(int i=0;i<n;i++){
    int c = S[i]-'a';
    int cur = ++s_sz;
    s_len[cur] = s_len[s_last]+1;
    bhead[s_len[cur]]++;
    mxo[cur] = (u32)(i+1);
    s_own[i] = (u32)cur;
    int p = s_last;
    for(; p && !sget(p,c); p = (int)s_link[p]) sset(p,c,cur);
    if(!p) s_link[cur] = 1;
    else {
      int q = sget(p,c);
      if((int)s_len[p]+1 == (int)s_len[q]) s_link[cur] = (u32)q;
      else {
        int cl = ++s_sz;
        s_len[cl] = s_len[p]+1; s_link[cl] = s_link[q];
        bhead[s_len[cl]]++;
        mxo[cl] = 0;
        memcpy(s_nxt + (size_t)cl*65, s_nxt + (size_t)q*65, 65);
        for(; p && sget(p,c)==q; p = (int)s_link[p]) sset(p,c,cl);
        s_link[q] = (u32)cl; s_link[cur] = (u32)cl;
      }
    }
    s_last = cur;
  }
}

// ======================= SAM of T, rebuilt per query (dense) ==============
static u8 t_nxt[(2*MAXT+10)*80] __attribute__((aligned(16)));
static u32 t_len[MAXTT], t_link[MAXTT];
static int t_sz, t_last, t_fresh;
static inline int tget(int p, int c){
  u32 x; __builtin_memcpy(&x, t_nxt + (size_t)p*80 + (size_t)c*3, 4);
  return (int)(x & 0xFFFFFFu);
}
static inline void tset(int p, int c, int t){
  size_t off = (size_t)p*80 + (size_t)c*3;
  u32 x; __builtin_memcpy(&x, t_nxt + off, 4);
  x = (x & 0xFF000000u) | ((u32)t & 0xFFFFFFu);
  __builtin_memcpy(t_nxt + off, &x, 4);
}
static inline void tzero(int p){
  if(p>t_fresh){t_fresh=p;return;}
  u8* row = t_nxt + (size_t)p*80;
  __m128i z = _mm_setzero_si128();
  _mm_store_si128((__m128i*)(row+0), z);
  _mm_store_si128((__m128i*)(row+16), z);
  _mm_store_si128((__m128i*)(row+32), z);
  _mm_store_si128((__m128i*)(row+48), z);
  _mm_store_si128((__m128i*)(row+64), z);
}

// ============ suffix-link tree: len-bucket lists + two linear passes ======

static int s_sn;

// ---- counting sort of the states by len (replaces the bucket linked list) ----
// ord_ ends up len-ASCENDING, so pass 1 (bottom-up mxo) walks it backwards and
// pass 2 (top-down preorder) walks it forwards.  No linked list => no serial
// pointer chase in the sweep, and no random write per state during construction.
static void build_ord(void){
  int n = s_sn;
  u32 sum = 0;
  for(int L=0; L<=n; L++){ u32 c = bhead[L]; bhead[L] = sum; sum += c; }
  for(u32 v=1; v<=(u32)s_sz; v++){ ord_[bhead[s_len[v]]++] = v; }
  nord_ = (int)sum;
}
// Pass 1 (ALWAYS needed): mxo[v] = max own+1 over the subtree of v, by a
// len-descending sweep (children strictly before parents).  The same sweep
// records the visiting order into ord_[] (sequential stores), so pass 2 never
// has to re-walk the bucket chains.
static void build_meta(void){          // bottom-up: children (larger len) first
  for(int i = nord_-1; i >= 0; i--){
    u32 v = ord_[i];
    u32 p = s_link[v];
    if(p && mxo[v] > mxo[p]) mxo[p] = mxo[v];
  }
}
// Pass 2 (LAZY): subtree sizes + preorder numbers.  Only the range-max over
// [tin,tout) uses these, so they are built at the first query that actually
// needs a range-max.  ord_[] is len-descending, so forward = bottom-up sizes,
// backward = top-down preorder.
static void build_intervals(void){
  // szsub[] is initialised here instead of in build_sam_s: it is only ever read by
  // this function, so the per-state store in the construction loop (and the 2.4 MB of
  // pages it dirtied) is pure overhead on tests that never build the intervals.
  for(int i=0;i<nord_;i++) szsub[ord_[i]] = 1;
  szsub[1] = 0;   // state 1's size is never read (its link is 0), exactly as before
  for(int i=nord_-1;i>=0;i--){          // len-descending = bottom-up sizes
    u32 v = ord_[i]; u32 p = s_link[v];
    if(p) szsub[p] += szsub[v];
  }
  tin[1] = 1; nxt[1] = 2;
  for(int i=0;i<nord_;i++){             // len-ascending = parents first = preorder
    u32 v = ord_[i];
    if(v == 1) continue;
    u32 p = s_link[v];
    u32 t = nxt[p];
    tin[v] = t; tout[v] = t + szsub[v];
    nxt[p] = t + szsub[v];
    nxt[v] = t + 1;
  }
}

// ============ range max over the Euler array (fused block scans) ============
// Replaces the earlier "block prefix/suffix arrays + segment tree over blocks".
// MEASURED on the real judge (tools/probe.py, n=5e5 random 26-letter S, cycles):
//   old eactivate  70.15M   old build_meta 15.58M  old build_intervals 22.38M
//   old qmax ~96 cyc/call
// The old activation wrote a whole 64-entry prefix block AND a whole 64-entry
// suffix block per activation (512 B = 8 cache lines of RFO traffic), plus a
// 15-level segment-tree update -- 140 cycles per activation.  With plain block
// scans the activation is 3 stores (one cold, two L1-resident) and the segment
// tree disappears.
#define EBS 8
#define EBSH 3
#define GBS 128
#define GBSH 7
#define ENB ((MAXST>>EBSH)+8)
#define ESB ((ENB>>GBSH)+8)
static u32 ev[MAXST+8];
static u32 ebmax[ENB+8];
static u32 eb2[ESB+8];

static inline void eactivate(int leaf, u32 val){
  ev[leaf] = val;
  int b = leaf >> EBSH;
  ebmax[b] = val;
  eb2[b >> GBSH] = val;
}
#define AVX2T __attribute__((target("avx2")))
AVX2T static inline __m256i ldu256(const void *p){
  __m256i r; __asm__("vmovdqu %1, %0" : "=x"(r) : "m"(*(const __m256i *)p)); return r; }
// accumulate max over p[0..n) into acc for ANY n>=0 (n<8 must not use the
// overlapping tail load -- it would read BEFORE p and pick up foreign values)
AVX2T static inline __m256i accblk(__m256i acc, const u32* p, int n){
  if(n <= 0) return acc;
  if(n < 8){
    for(int i=0;i<n;i++) acc = _mm256_max_epu32(acc, _mm256_set1_epi32((int)p[i]));
    return acc;
  }
  int i = 0;
  for(; i+8 <= n; i += 8) acc = _mm256_max_epu32(acc, ldu256(p+i));
  if(i < n) acc = _mm256_max_epu32(acc, ldu256(p+n-8));   // overlapping tail load
  return acc;
}
AVX2T static inline u32 red256(__m256i acc){
  __m128i lo = _mm256_castsi256_si128(acc), hi = _mm256_extracti128_si256(acc,1);
  __m128i m = _mm_max_epu32(lo,hi);
  m = _mm_max_epu32(m, _mm_shuffle_epi32(m,_MM_SHUFFLE(1,0,3,2)));
  m = _mm_max_epu32(m, _mm_shuffle_epi32(m,_MM_SHUFFLE(2,3,0,1)));
  return (u32)_mm_cvtsi128_si32(m);
}
AVX2T static inline u32 scanmax(const u32* p, int n){
  if(n <= 0) return 0;
  return red256(accblk(_mm256_setzero_si256(), p, n));
}
static inline u32 qmax(int l, int r){          // max over [l,r)
  if(l>=r) return 0;
  int b1=l>>EBSH, b2=(r-1)>>EBSH;
  if(b1==b2) return scanmax(ev+l, r-l);
  __m256i acc = _mm256_setzero_si256();
  acc = accblk(acc, ev+l, ((b1+1)<<EBSH) - l);
  int j = r & (EBS-1);
  if(j) acc = accblk(acc, ev+(b2<<EBSH), j);
  else  acc = accblk(acc, ebmax+b2, 1);
  int lo=b1+1, hi=b2, cnt=hi-lo;             // whole blocks [lo,hi)
  if(cnt > 0){
    if(cnt <= GBS){
      acc = accblk(acc, ebmax+lo, cnt);
    } else {
      int s1=(lo+GBS-1)&~(GBS-1), s2=hi&~(GBS-1);
      if(s1>lo) acc = accblk(acc, ebmax+lo, s1-lo);
      if(s2>s1) acc = accblk(acc, eb2+(s1>>GBSH), (s2-s1)>>GBSH);
      if(hi>s2) acc = accblk(acc, ebmax+s2, hi-s2);
    }
  }
  return red256(acc);
}

// ============================== query handling ============================
struct QE { const char* t; int tl, l, r, idx; };
static QE qs[MAXQ];
static QE qs2[MAXQ];
static long long answers[MAXQ];
static int f_[MAXS];
static int cnt_[MAXS+2];

static char* OUTP;
static const char D2[201] =
  "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
  "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
  "8081828384858687888990919293949596979899";
static inline void emit(long long v){
  char b[24]; int c=0;
  if(v==0){ *OUTP++='0'; *OUTP++='\n'; return; }
  while(v >= 100){
    unsigned r = (unsigned)(v % 100); v /= 100;
    b[c++] = D2[r*2+1]; b[c++] = D2[r*2];
  }
  if(v >= 10){ unsigned r = (unsigned)v; b[c++] = D2[r*2+1]; b[c++] = D2[r*2]; }
  else if(v > 0){ b[c++] = (char)('0' + (int)v); }
  while(c) *OUTP++ = b[--c];
  *OUTP++='\n';
}

static inline const char* letters_end(const char*p,const char*e){
 while(e-p>=32){__m256i v=ldu256(p);u32 m=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8('a'),v));if(m)return p+__builtin_ctz(m);p+=32;}
 while(p<e&&*p>='a'&&*p<='z')p++;return p;
}
static void run(const u8* in, ul insz, char* out){
  const char* p = (const char*)in;
  const char* e = p + insz;
  OUTP = out;

  while(p<e && (*p<'a'||*p>'z')) p++;
  const char* sstart = p;
  p=letters_end(p,e);
  int sn = (int)(p - sstart);
  build_sam_s(sstart, sn);

  while(p<e && (*p<'0'||*p>'9')) p++;
  int Q=0;
  while(p<e && *p>='0'&&*p<='9'){ Q = Q*10 + (*p-'0'); p++; }
  if(Q>MAXQ) Q=MAXQ;

  for(int i=0;i<Q;i++){
    while(p<e && (*p<'a'||*p>'z')) p++;
    const char* ts = p;
    p=letters_end(p,e);
    int tl = (int)(p-ts);
    if(tl>MAXT) tl=MAXT;
    while(p<e && (*p<'0'||*p>'9')) p++;
    int l=0; while(p<e && *p>='0'&&*p<='9'){ l=l*10+(*p-'0'); p++; }
    while(p<e && (*p<'0'||*p>'9')) p++;
    int r=0; while(p<e && *p>='0'&&*p<='9'){ r=r*10+(*p-'0'); p++; }
    qs[i].t = ts; qs[i].tl = tl; qs[i].l = l; qs[i].r = r; qs[i].idx = i;
  }

  s_sn = sn;
  int sz = s_sz;
  // ---- strategy choice ---------------------------------------------------
  // The ancestor-painting routes are KEPT in the file but no longer selected:
  // real-judge measurement showed their cost is sum_i depth(s_own[i]) steps, which
  // the 256-sample estimate can under-predict (a deep tree blows it up ~4x), while
  // the Euler route is now bounded and cheap: with the block-scan activation its
  // fixed cost is 34 cyc/state (intervals) + 20 cyc/activation + 113 cyc/qmax.
  // Forcing the Euler route makes the tree phase predictable instead of data-dependent.
  wl_mode = 0; wl_budget = 0;
  build_ord();
  if(!wl_mode) build_meta();
  eul_ready = 0;
  // ev / ebmax / etree are zero initialized (BSS): no clearing needed

  { // counting sort of the queries by r
    int mx = sn+1;
    memset(cnt_, 0, (size_t)(mx+2)*4);
    for(int i=0;i<Q;i++){ int rr = qs[i].r; if(rr<0) rr=0; if(rr>mx) rr=mx; cnt_[rr]++; }
    int acc=0;
    for(int i=0;i<=mx;i++){ int c=cnt_[i]; cnt_[i]=acc; acc+=c; }
    for(int i=0;i<Q;i++){ int rr = qs[i].r; if(rr<0) rr=0; if(rr>mx) rr=mx; qs2[cnt_[rr]++] = qs[i]; }
  }

  int act = 0;   // positions < act already activated
  long long wl_work = 0;
  for(int qi=0; qi<Q; qi++){
    const QE& q = qs2[qi];
    int need = q.r;                 // activate positions 0..r-1
    if(need > sn) need = sn;
    if(need < 0) need = 0;
    int npaint = 0;
    if(wl_mode == 2){
      // downward sweep, stop at the first state already painted this query:
      // the first state painted gets the largest own+1, which is exactly MX(x, need)
      for(int i=need-1;i>=0;i--){
        int a = (int)s_own[i]; u32 val = (u32)(i+1);
        while(a != 1 && !wl_last[a]){ wl_last[a] = val; plist_[npaint++] = (u32)a; a = (int)s_link[a]; }
      }
    } else if(wl_mode){
      for(; act<need; act++){
        int a = (int)s_own[act]; u32 val = (u32)(act+1);
        wl_last[a] = val; wl_work++;
        while(a != 1){ a = (int)s_link[a]; wl_last[a] = val; wl_work++; }
        if(wl_work > wl_budget){ wl_mode = 0; break; }   // blew the budget
      }
      if(!wl_mode){                 // fell back mid-activation: replay into the Euler struct
        build_meta(); build_intervals(); eul_ready = 1;
        for(int i=0;i<act;i++){ int v = (int)s_own[i]; eactivate((int)tin[v], (u32)(i+1)); }
        for(; act<need; act++){ int v = (int)s_own[act]; eactivate((int)tin[v], (u32)(act+1)); }
      }
    } else if(eul_ready){
      for(; act<need; act++){
        int v = (int)s_own[act];
        eactivate((int)tin[v], (u32)(act+1));
      }
    } else if(need > act) act = need;
    const char* T = q.t;
    int tl = q.tl;
    int l0 = q.l - 1;
    int r1 = q.r - 1;
    int maxlen = q.r - q.l + 1;
    if(maxlen < 0) maxlen = 0;
    int v = 1, len = 0, e = -1;   // e = witness end position of the current match
    // ARM FULLRANGE (this seat).  For a FULL-RANGE query (l == 1 && r >= |S|) the interval
    // clip can never shorten the match: mxo[v] >= s_len[v] >= len holds for every state, so
    // the clip's `lim >= len` test fires on its very first iteration and leaves len alone,
    // and maxlen = q.r - q.l + 1 >= |S| >= len makes the `len > maxlen` branch unreachable.
    // The clip therefore degenerates to "record the witness e", and the witness feeds only
    // the fast path -- which is itself a pure shortcut: whenever it fires, sget(v,c) != 0
    // (the match extending at the witness is an occurrence of match+c in S), so the generic
    // walk below exits on its FIRST test with exactly the same (v,len).  Both are dead
    // weight on this shape, and dropping them removes one mxo[] load per character plus the
    // sstart[]/e bookkeeping from the loop that is 61% of tc17's runtime.
    // Measured on this exact shape (|S|=5e5, |T|=1e6, l=1, r=|S|): the fast path fires
    // 38,424 / 1,000,000 characters = 3.8%, and the clip runs 1.000 iterations per
    // slow-path character => ~1.9 random loads/char are being paid for a 3.8% shortcut.
    const int full_range = (l0 == 0 && q.r >= sn);
    for(int i=0;i<tl;i++){
      int c = T[i]-'a';
      int nx=sget(v,c);
      int vn=(int)s_link[v];
      if(__builtin_expect(full_range,1)){
        int ov = v;
        while(v!=1 && !nx) { v = vn; vn = (int)s_link[v]; nx=sget(v,c); }
        if(v != ov) len = (int)s_len[v];
        if(nx){ v = nx; len++; } else { v = 1; len = 0; }
        f_[i] = len;
        continue;
      }
      // fast path: the match extends in place at the witness (f[i] <= f[i-1]+1, so len+1 is optimal)
      if(len > 0 && e < r1 && sstart[e+1]-'a' == c){
        v = nx; len++; e++;
        f_[i] = len;
        continue;
      }
      // Only the FINAL rung of this walk matters: `len` is rewritten on every step
      // but read only after the loop, and once at least one step ran len == s_len[v].
      // Reading s_len[] inside the loop therefore costs one extra random load per rung
      // into a *separate* 2.4 MB array (one more TLB entry + one more miss) for
      // nothing.  The sget below is the very address the walk just tested => L1 hit.
      {
        int ov = v;
        // ARM LNKLA: software-pipeline the suffix-link chase.  The old form loaded
        // s_link[v] only after the sget test failed, so each rung's link load sat on the
        // critical path behind the previous rung.  Fetching the next link up front makes
        // the two loads of a rung independent, which is exactly the shape the current
        // board leader uses (ref2/rival_107908.cpp, `int vn = (int)s_link[v];` hoisted
        // above the test).  `len` handling is unchanged: read once, at the rung we stop on.
        while(v!=1 && !nx) { v = vn; vn = (int)s_link[v]; nx=sget(v,c); }
        if(v != ov) len = (int)s_len[v];
      }
      if(nx){ v = nx; len++; } else { v = 1; len = 0; }
      e = -1;
      // clip the match to S[l..r]: longest suffix whose endpos hits [l+len-1, r-1]
      while(len>0){
        if(len > maxlen){
          len = maxlen;
          while(v != 1 && len <= (int)s_len[s_link[v]]) v = (int)s_link[v];
          if(len == 0) break;
        }
        u32 m;
        if(mxo[v] <= (u32)q.r) m = mxo[v];
        else if(mxo[v]==s_len[v]) m=0;
        else {
          if(!eul_ready){
            build_intervals();
            for(int i2=0;i2<act;i2++){ int vv=(int)s_own[i2]; eactivate((int)tin[vv], (u32)(i2+1)); }
            eul_ready = 1;
          }
          m = qmax((int)tin[v],(int)tout[v]);
        }
        // lengths in this state's class that can still satisfy the test
        int lim = (int)m - l0;
        if(lim >= len){ e = (int)m - 1; break; }
        int pl = (int)s_len[s_link[v]];
        if(lim > pl){ len = lim; e = (int)m - 1; break; }
        len = pl;
        if(len == 0) break;
        v = (int)s_link[v];
      }
      f_[i] = len;
    }
    if(wl_mode == 2){ for(int k=0;k<npaint;k++) wl_last[plist_[k]] = 0; }
    // SAM(T) -> g[], accumulate
    t_sz=1; t_last=1;
    t_len[1]=0; t_link[1]=0;
    tzero(1);
    long long ans=0;
    for(int i=0;i<tl;i++){
      int c = T[i]-'a';
      int cur = ++t_sz;
      t_len[cur] = t_len[t_last]+1; t_link[cur]=0;
      tzero(cur);
      int pp = t_last;
      for(; pp && !tget(pp,c); pp = (int)t_link[pp]) tset(pp,c,cur);
      int lk;
      if(!pp) lk = 1;
      else {
        int qq = tget(pp,c);
        if((int)t_len[pp]+1 == (int)t_len[qq]) lk = qq;
        else {
          int cl = ++t_sz;
          if(cl>t_fresh)t_fresh=cl;
          t_len[cl] = t_len[pp]+1; t_link[cl] = t_link[qq];
          memcpy(t_nxt + (size_t)cl*80, t_nxt + (size_t)qq*80, 80);
          for(; pp && tget(pp,c)==qq; pp = (int)t_link[pp]) tset(pp,c,cl);
          t_link[qq] = (u32)cl; lk = cl;
        }
      }
      t_link[cur] = (u32)lk;
      t_last = cur;
      int g = (int)t_len[lk];
      int m = g > f_[i] ? g : f_[i];
      ans += (long long)(i+1) - m;
    }
    answers[q.idx] = ans;
  }
  for(int i=0;i<Q;i++) emit(answers[i]);
}

#pragma GCC pop_options

#ifndef LOCAL
int main(){ return 0; }
extern "C" void __libc_start_main(void*mm,int argc,char**argv){
  ul *p=(ul*)(argv+argc+1);
  while(*p) p++; p++;
  DI *d=0; for(; p[0]; p+=2) if(p[0]==0x6b637564UL){ d=(DI*)p[1]; break; }
  if(d){
    const u8* in=(const u8*)d->IBp; ul insz=d->IBl;
    if(!insz && d->is){ in=(const u8*)d->ip; insz=d->is; }
    run(in,insz,d->op);
    d->os=(ul)(OUTP-d->op);
  }
  __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
  for(;;);
}
#endif

评测结果