/* References: saffah_cc_v41_agg1 https://duck.ac/submission/121232,
reused the suffix-automaton engine and bounded early-exit witness scan. All
inherited source credits remain below. No independent license declared.
Idea: Handle witness ranges of one or two entries with direct scalar compares,
returning the same first qualifying value. These ranges do not benefit from
the masked vector load, compare, movemask and trailing-zero extraction.
Purpose: Remove vector setup for the common shortest witness ranges.
*/
// ===== REFERENCES =====
// [0] 【本发的引用对象】duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #121138
// <https://duck.ac/submission/121138> —— **本文件正文 = #121138 的逐位复刻**（含其全部血缘），
// 本席只加一处 ARM FP（见下「思路」）。#121138 的正文本身也带它自己的 REFERENCES/思路 两块，
// 为避免与本块重复，那两块被整理进下面的 [1]~[5]，全部 URL 与账号一字未改。
// [1]~[4] 为 #121138 自带的引用块（原文保留，含许可证说明）：
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #120833 <https://duck.ac/submission/120833>
// 用途：**本文件正文的直接来源**（本席入场时榜首 T = 117.142328 ms）。本席取回其公开源码后
// 与本账号在册最好件 #120430 逐行 diff，分解为：
// · 真改动 3 处：①`letters_end()` 用一条 32 字节 SIMD 分隔符掩码定位小写串末尾（替代逐字节
// 扫描）；②`t_fresh` 高水位：首次使用的 t_nxt 行本就在 BSS 里是 0，跳过冗余清零；
// ③`short_masks[8][8]`：EBS 块内 n∈[3,7] 的部分块改用一次掩码向量载入，`scanmax` 对
// n==1/n==2 走标量，避开水平归约。三处**原样保留**在正文中（见下）。
// · 落后量 0（他抄的正是我方最新件）· 有害改动 0。
// ⇒ 属 `§2.18.349` 的"对手抄我方最新件"型：**抄件上限 = 对手件本身 = 117.142328 ms，仍高于
// 严支 115.971905 ms ⇒ 纯抄不可能达标**，故本发 = 抄下它 + 本席自己的一刀（ARM-QB，见 思路）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #120430 <https://duck.ac/submission/120430>
// 用途：直接父件的父件 / 本文件正文的血缘（ARM FULLRANGE：整区间询问裁掉见证与裁剪机制）。
// 其自带的 REFERENCES / 思路 两块**原样保留**在下方，引用链完整可溯。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107930 <https://duck.ac/submission/107930>
// 与 #107908：血缘（s_nxt 20 位打包 · t_nxt 3 字节打包 · 计数排序代替桶链表 · 回退链链接前瞻
// LNKLA），其引用块亦原样保留。
// [4] `problems/noi18c/notes.md`（第三/四轮相位账 + `e18d_`/`o18d_` 席结论）用途：tc17 = 解析+SAM(S)
// 35.28 ms | build_ord+meta 4.00 | 匹配 f[] 85.63（61%）| SAM(T)+累加 13.78 | emit 0.54；
// 以及"本族对地址足迹/访存条数敏感、对步长放大极敏感"的既有结论。
// 许可证：以上均为 duck.ac 公开提交与公开题面，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径（`python3 tools/exact.py noi18c`，判题机原值，入场时现读）】
// mine = **117.075720**（#121138 本账号）· T = **117.142328**（#120833 saffah_codex_6a_agg3）
// ⇒ 宽支 1.005*T+1 = 117.729040 已被我方新件锁掉 ⇒ **真栏 = 0.99*T+1µs = 115.971905**，
// 差 **1.103815 ms（0.943%）**。
//
// 【本发 = #121138 正文（逐位复刻，含其全部血缘）＋ 本席唯一一刀 ARM FP】
//
// 【★ 结构性诊断（本机插桩，|S|=5e5 随机 26 字母 · Q=1e5 · Σ|T|=1e6 · l,r 随机 = tc16/17 形状）】
// · qmax 被调用 **986,394 次 / 1e6 字符**；clip 迭代 **1,327,969** 次，其中
// `mxo[v] <= q.r` 短路 **341,575** 次（26%）、**case1（lim>=len，即匹配不缩短）965,386 次（72.7%）**、
// **case2（lim>pl，唯一需要 m 精确值的那一支）0 次**、case3（缩小并沿 link 上爬）362,583 次。
// · ⇒ **精确最大值从来不是必需的**：case1 只需要"存在某个被激活叶 ≥ len+l0"这件事**加上一个见证**，
// case3 根本不用 m。基线却为此每次调用都扫完整个区间（均值约 20 条 32B 取数）。
// · 见证分布（在 ebmax 项上从左往右数，第一个 ≥ len+l0 的项）：**均值 4.45 项**，
// **68.2% 的调用落在第 1 条向量（8 项）之内**，13.7% 的调用整段都不存在这样的项。
// ⇒ 命中是**稠密**的：一次提前退出就能把 72.7% 的决策在 1~2 条向量内做完。
//
// 【ARM FP：`qf(l,r,X,&w)` = 提前退出的谓词扫描】
// 扫描次序按"便宜且命中率高"排：①左边界叶块（≤8 叶，1 条掩码向量）
// ②ebmax 中段 [b1+1,b2) 的前 QF_BUD 项（8 项/条向量，命中即退出并取见证）
// ③右边界叶块 / `ebmax[b2]`。任一步命中即返回该**被激活叶的值** w（≥ X = len+l0）。
// 全部落空 ⇒ 退回原来的 `qmax` 全扫（**语义不变**：case2 仍拿到精确 m）。
// · 见证合法性：`ebmax[b]` 由 `eactivate` 以"后写覆盖"维护，而激活按位置递增 ⇒ 它正是块内某个
// **被激活叶的值**；叶块内的元素亦同。区间 [l,r) 内的任一被激活叶值都是该状态的合法 endpos+1，
// 而 case1 只需 lim = w-l0 >= len，故 w 不必是最大值（快路 `sstart[e+1]==c` 用的是"存在性"，与取值无关）。
// · QF_BUD = 32（4 条向量）：命中率已覆盖 68%+，而未命中时的浪费被封顶。
//
// 【判题机定价（**一次同进程四臂探针**，`o18f_probe1_full.cpp`，判题机 293.4 ms / 75 MB）】
// 同一二进制、同一数据、臂序轮转（0,1,2,3,2,3,0,1），rdtsc 只包住 query 循环（单位：tick，TSC 3.53 GHz）：
// arm0 = 基线 qmax 113,403,130 / 112,825,822
// arm1 = qf bud=8 108,197,726 / 108,176,306
// arm2 = qf bud=32 107,453,346 / 108,121,180
// arm3 = qf 无上限平面扫描 107,311,746 / 107,491,720
// 四臂 checksum 完全相同 ⇒ 逐位等价；**arm2 vs arm0 = −4.70%（两轮次序一致，判题机臂内离散 0.02~0.6%）**。
// ⇒ 这是本族第一个**用判题机同进程 A/B 直接定价**的刀（o18e_ 的 ARM-QB 是本地 −6.05%/Ir −3.11% 而板面 +1.75 ms，
// 两者都不迁移；本刀的读数直接来自判题机，且判题机 TSC 频率 3.53 GHz 已用 293.4 ms 墙钟反解标定）。
//
// 【正确性闸门（全过）】
// · 本机 **93 组语料**（`/home/yjp/duck.ac/.cache/n1b/cv/`）输出与本账号 #121138 正文**逐字节相同（93/93）**。
// · 同进程四臂探针在两组独立随机数据（|S|=5e5 · Q=1e5 与 Q=2e4）上 checksum 全同；
// 探针程序自身的 checksum 又与独立参考件多项式哈希对拍一致。
// · `qf` 只在 `mxo[v] > q.r` 的既有分支内替换取值来源，未命中即回落原函数 ⇒ 除 case1 的见证取值外无处改变语义。
// ======================
#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)
static const u32 short_masks[8][8] __attribute__((aligned(32)))={{0,0,0,0,0,0,0,0},{0xffffffffu,0,0,0,0,0,0,0},{0xffffffffu,0xffffffffu,0,0,0,0,0,0},{0xffffffffu,0xffffffffu,0xffffffffu,0,0,0,0,0},{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0,0,0},{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0,0},{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0},{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0}};
AVX2T static inline __m256i accblk(__m256i acc, const u32* p, int n){
if(n <= 0) return acc;
if(n < 8){
if(n>=3)return _mm256_max_epu32(acc,_mm256_and_si256(ldu256(p),_mm256_load_si256((const __m256i*)short_masks[n])));
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;
if(n==1)return p[0];
if(n==2)return p[0]>p[1]?p[0]:p[1];
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);
}
// ================= o18f_ ARM FP: early-exit predicate on the Euler range =====
// qf(l,r,X,&w) answers "does some ACTIVATED leaf in [l,r) hold a value >= X",
// returning one such value in *w. It scans the cheapest sources first and stops
// at the first hit, so the common clip decision (lim >= len) is settled after
// 1-2 vector loads instead of a full two-level pyramid sweep.
static inline int anyge(const u32* p, int n, u32 X, u32* w){
if(n <= 0) return 0;
if(n<=2){u32 v=p[0];if(v>=X){*w=v;return 1;}if(n==2){v=p[1];if(v>=X){*w=v;return 1;}}return 0;}
__m256i xm1 = _mm256_set1_epi32((int)X-1);
if(n >= 8){
int i=0;
for(; i+8 <= n; i += 8){
__m256i v = ldu256(p+i);
unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
}
if(i < n){
int t = n-i;
__m256i v = _mm256_and_si256(ldu256(p+i), _mm256_load_si256((const __m256i*)short_masks[t]));
unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
}
return 0;
}
__m256i v = _mm256_and_si256(ldu256(p), _mm256_load_si256((const __m256i*)short_masks[n]));
unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
if(mk){ *w = p[__builtin_ctz(mk)]; return 1; }
return 0;
}
#define QF_BUD 32
static inline int qf(int l, int r, u32 X, u32* w){
if(l >= r) return 0;
int b1=l>>EBSH, b2=(r-1)>>EBSH;
if(b1==b2) return anyge(ev+l, r-l, X, w);
if(anyge(ev+l, ((b1+1)<<EBSH) - l, X, w)) return 1;
int lo=b1+1, hi=b2, nb=hi-lo; int lim = nb<QF_BUD?nb:QF_BUD;
if(lim>0 && anyge(ebmax+lo, lim, X, w)) return 1;
int j=r&(EBS-1);
if(j){ if(anyge(ev+(b2<<EBSH), j, X, w)) return 1; }
else if(ebmax[b2]>=X){ *w = ebmax[b2]; return 1; }
return 0;
}
// ============================== 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(!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;
}
u32 _w;
if(qf((int)tin[v],(int)tout[v], (u32)(len+l0), &_w)) m = _w;
else 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