// fast.cpp -- optimised variant of sol/noi18c/correct.cpp (md5 82b3cd77460f408ca9d7f3b2f62003ed)
// Output is byte-identical to correct.cpp on lab/noi18c/q17.txt, q17b.txt, qbig.txt.
//
// What is changed (everything else is untouched):
// 1) SAM(S) table `ch` and SAM(T) table `tch`: vector<int>(N, 0) -> calloc().
// The eager zero-fill of the 104 MB S-table cost ~2.1e8 cycles (~0.055 s); with a
// lazily-zeroed calloc that work is spread over the pages actually touched.
// 2) interval-max decomposition rewritten as a hybrid (stInit/stSet/stMax):
// level 0 keeps eager pre0/suf0 (B0=16 positions = 1 cache line) so boundary blocks
// are two loads, while the upper levels (B1=16 blocks/super-block, B2=64
// super-blocks/mega-block) are plain "newest activation" summaries queried by short
// scans -- activations have strictly increasing values, so every summary is one
// store and the eager pre1/suf1 arrays + segment tree of correct.cpp are gone.
// 3) len/link/lastPos/tin/szsub/ord/cstart/childList/cpos/tlen/tlink -> raw malloc/calloc
// (no redundant zero-init where every used element is written anyway).
// (initial capacity of szsub is still filled with 1)
//
// Measured on this box (interleaved, min of 7 runs, correct.cpp -> fast.cpp):
// q17 : 0.50 -> 0.45 s q17b : 0.43 -> 0.42 s qbig : 0.44 -> 0.40 s
//
// NEGATIVE RESULT (do not repeat): replacing the SAM(S) table with the compact
// mask/base/packed-target representation (u64 mb[state] = mask<<32|base, targets in a
// pool, rank = popcount(mask & ((1<<c)-1))) is byte-correct but SLOWER end to end
// (q17 0.54 vs 0.51): the 104 MB zero-init saving (~2.1e8 cycles) is more than eaten by
// the per-transition insert (segment shift + grow) and the two dependent loads per
// lookup during construction/matching: build loop 1.5e8 -> 3.3e8 cycles.
//
// Phase profile of correct.cpp on q17 (TSC cycles, ~3.8e9/s):
// SAM(S) alloc 2.1e8 + build 1.5e8 | link tree 2.0e8 | query loop 1.1e9
// of which stSet 1.7e8, stMax 3.9e8, SAM(T) 0.9e8, dirty-clear 0.35e8,
// matching 2.2e8, per-query bookkeeping ~2e8
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
static char pad[64 << 20];
static inline void dumpv(ull v) { volatile char *p = pad; for (ull i = 0; i < v; i++) p[i * 4096] = 1; }
// ---------- input (whole buffer) ----------
static char inbuf[1 << 23];
static size_t inpos = 0;
static inline int gc() { return (unsigned char)inbuf[inpos++]; }
static inline int rdint() {
while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
int x = 0;
while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
return x;
}
static const int AL = 26;
// ---------- range max over activated positions (hybrid) ----------
// Activations arrive with strictly increasing values, so every upper-level summary is
// just "the newest activation inside it" (one store). Level 0 keeps pre0/suf0 arrays so
// a query's partial blocks are answered by two loads; the upper levels use summaries and
// short scans instead of eagerly maintained prefix/suffix arrays / segment tree.
// val[pos] : activation value (0 = not activated)
// pre0/suf0 : prefix/suffix max inside the 1-cache-line position block
// bmax0[b] : newest activation in block b (L0 positions)
// smax[s] : newest activation in super-block s (L1 blocks)
// mmax[g] : newest activation in mega-block g (L2 super-blocks)
static const int B0 = 16; // positions per block (16 ints = 1 cache line)
static const int B1 = 16; // blocks per super-block
static const int B2 = 64; // super-blocks per mega-block
static int nb0, nsb, ngb;
static int *val, *pre0, *suf0, *bmax0, *smax, *mmax;
static void stInit(int n) {
nb0 = (n + B0 - 1) / B0;
nsb = (nb0 + B1 - 1) / B1;
ngb = (nsb + B2 - 1) / B2;
val = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
pre0 = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
suf0 = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
bmax0 = (int *)calloc((size_t)nb0 + 2, sizeof(int));
smax = (int *)calloc((size_t)nsb + 2, sizeof(int));
mmax = (int *)calloc((size_t)ngb + 2, sizeof(int));
}
static inline void stSet(int pos, int v) { // v strictly increasing over calls
val[pos] = v;
int b = (pos - 1) / B0, s = b * B0 + 1, e = s + B0 - 1, q;
for (q = s; q <= pos; q++) suf0[q] = v;
for (q = pos; q <= e; q++) pre0[q] = v;
bmax0[b] = v;
int sb = b / B1;
smax[sb] = v;
mmax[sb / B2] = v;
}
static inline int stMax(int l, int r) {
int b0l = (l - 1) / B0, b0r = (r - 1) / B0, i;
if (b0l == b0r) {
const int *v = val;
int res = 0;
for (i = l; i <= r; i++) if (v[i] > res) res = v[i];
return res;
}
int res = suf0[l] > pre0[r] ? suf0[l] : pre0[r];
int a = b0l + 1, bb = b0r - 1;
if (a > bb) return res;
int s0 = a / B1, s1 = bb / B1;
if (s0 == s1) {
const int *bm = bmax0;
for (i = a; i <= bb; i++) if (bm[i] > res) res = bm[i];
return res;
}
{ const int *bm = bmax0;
int e0 = (s0 + 1) * B1;
for (i = a; i < e0; i++) if (bm[i] > res) res = bm[i];
for (i = s1 * B1; i <= bb; i++) if (bm[i] > res) res = bm[i];
}
int m0 = s0 + 1, m1 = s1 - 1;
if (m0 > m1) return res;
int g0 = m0 / B2, g1 = m1 / B2;
if (g0 == g1) {
const int *sm = smax;
for (i = m0; i <= m1; i++) if (sm[i] > res) res = sm[i];
return res;
}
{ const int *sm = smax;
int e0 = (g0 + 1) * B2;
for (i = m0; i < e0; i++) if (sm[i] > res) res = sm[i];
for (i = g1 * B2; i <= m1; i++) if (sm[i] > res) res = sm[i];
}
{ const int *gm = mmax;
for (i = g0 + 1; i < g1; i++) if (gm[i] > res) res = gm[i];
}
return res;
}
int main() {
{
size_t len = 0, r;
while (len < sizeof(inbuf) - 1 && (r = fread(inbuf + len, 1, sizeof(inbuf) - 1 - len, stdin)) > 0) len += r;
inbuf[len] = 0;
}
// read S
string S;
{
int c = gc();
while (c != -1 && (c < 'a' || c > 'z')) c = gc();
while (c >= 'a' && c <= 'z') { S.push_back((char)c); c = gc(); }
}
int nS = (int)S.size();
int Q = rdint();
// read queries
vector<int> ql(Q), qr(Q), qoff(Q), qlen(Q);
string tbuf;
tbuf.reserve(1 << 20);
for (int q = 0; q < Q; q++) {
qoff[q] = (int)tbuf.size();
int c = gc();
while (c != -1 && (c < 'a' || c > 'z')) c = gc();
while (c >= 'a' && c <= 'z') { tbuf.push_back((char)c); c = gc(); }
qlen[q] = (int)tbuf.size() - qoff[q];
ql[q] = rdint();
qr[q] = rdint();
}
// ---------- SAM of S ----------
int maxSt = 2 * nS + 5;
int *len = (int *)malloc((size_t)maxSt * sizeof(int));
int *link = (int *)malloc((size_t)maxSt * sizeof(int));
int *ch = (int *)calloc((size_t)maxSt * AL, sizeof(int));
int *lastPos = (int *)malloc((size_t)(nS + 1) * sizeof(int));
int sz = 1, last = 1;
len[1] = 0; link[1] = 0;
for (int i = 0; i < nS; i++) {
int c = S[i] - 'a';
int cur = ++sz;
len[cur] = len[last] + 1;
link[cur] = 0;
int p = last;
while (p && !ch[(size_t)p * AL + c]) { ch[(size_t)p * AL + c] = cur; p = link[p]; }
if (!p) link[cur] = 1;
else {
int q = ch[(size_t)p * AL + c];
if (len[p] + 1 == len[q]) link[cur] = q;
else {
int clone = ++sz;
len[clone] = len[p] + 1;
link[clone] = link[q];
memcpy(&ch[(size_t)clone * AL], &ch[(size_t)q * AL], AL * sizeof(int));
while (p && ch[(size_t)p * AL + c] == q) { ch[(size_t)p * AL + c] = clone; p = link[p]; }
link[q] = clone;
link[cur] = clone;
}
}
last = cur;
lastPos[i + 1] = last;
}
// ---------- link tree: children (CSR) ----------
int *cstart = (int *)calloc((size_t)sz + 2, sizeof(int));
int *childList = (int *)malloc((size_t)sz * sizeof(int));
int *cpos = (int *)malloc(((size_t)sz + 2) * sizeof(int));
for (int v = 2; v <= sz; v++) cstart[link[v] + 1]++;
for (int v = 1; v <= sz; v++) cstart[v + 1] += cstart[v];
for (int v = 0; v <= sz + 1; v++) cpos[v] = cstart[v];
for (int v = 2; v <= sz; v++) childList[cpos[link[v]]++] = v;
// preorder + subtree sizes
int *tin = (int *)malloc((size_t)(sz + 1) * sizeof(int));
int *szsub = (int *)malloc((size_t)(sz + 1) * sizeof(int));
int *ord = (int *)malloc((size_t)(sz + 1) * sizeof(int));
for (int v = 0; v <= sz; v++) szsub[v] = 1;
vector<unsigned long long> mmE(sz + 1, ((unsigned long long)(nS + 1) << 20));
{
vector<int> stk;
stk.reserve(sz);
stk.push_back(1);
int timer = 0;
while (!stk.empty()) {
int v = stk.back(); stk.pop_back();
tin[v] = ++timer; ord[timer] = v;
for (int k = cstart[v]; k < cstart[v + 1]; k++) stk.push_back(childList[k]);
}
for (int i = 1; i <= nS; i++) { int u = lastPos[i]; mmE[u] = ((unsigned long long)i << 20) | (unsigned)i; }
for (int t = timer; t >= 1; t--) {
int v = ord[t];
int s = 1;
for (int k = cstart[v]; k < cstart[v + 1]; k++) {
int c2 = childList[k];
s += szsub[c2];
unsigned long long e2 = mmE[c2];
if ((e2 >> 20) < (mmE[v] >> 20)) mmE[v] = (mmE[v] & 0xFFFFFULL) | (e2 & ~0xFFFFFULL);
if ((e2 & 0xFFFFFULL) > (mmE[v] & 0xFFFFFULL)) mmE[v] = (mmE[v] & ~0xFFFFFULL) | (e2 & 0xFFFFFULL);
}
szsub[v] = s;
}
}
stInit(sz + 1);
// ---------- process queries grouped by r ----------
vector<int> qorder(Q);
for (int q = 0; q < Q; q++) qorder[q] = q;
sort(qorder.begin(), qorder.end(), [&](int x, int y) { return qr[x] < qr[y]; });
vector<ll> res(Q, 0);
// SAM of T buffers (reused)
int maxT = 0;
for (int q = 0; q < Q; q++) maxT = max(maxT, qlen[q]);
int tmaxSt = 2 * maxT + 5;
int *tlen = (int *)malloc((size_t)tmaxSt * sizeof(int));
int *tlink = (int *)malloc((size_t)tmaxSt * sizeof(int));
int *tch = (int *)calloc((size_t)tmaxSt * AL, sizeof(int));
vector<int> tdirty;
tdirty.reserve((size_t)tmaxSt * 2);
int qi = 0;
for (int r = 1; r <= nS && qi < Q; r++) {
stSet(tin[lastPos[r]], r);
while (qi < Q && qr[qorder[qi]] == r) {
int q = qorder[qi++];
int m = qlen[q];
const char *T = tbuf.data() + qoff[q];
int qq = ql[q];
// build SAM of T on the fly, match against SAM(S)
int tsz = 1, tlast = 1;
tlen[1] = 0; tlink[1] = 0;
for (size_t z = 0; z < tdirty.size(); z++) tch[tdirty[z]] = 0;
tdirty.clear();
ll ans = 0;
int v = 1, L = 0;
for (int i = 1; i <= m; i++) {
int c = T[i - 1] - 'a';
// --- insert into SAM of T ---
{
int cur = ++tsz;
tlen[cur] = tlen[tlast] + 1;
tlink[cur] = 0;
int p = tlast;
while (p && !tch[(size_t)p * AL + c]) {
tch[(size_t)p * AL + c] = cur;
tdirty.push_back((int)((size_t)p * AL + c));
p = tlink[p];
}
if (!p) tlink[cur] = 1;
else {
int qq2 = tch[(size_t)p * AL + c];
if (tlen[p] + 1 == tlen[qq2]) tlink[cur] = qq2;
else {
int clone = ++tsz;
tlen[clone] = tlen[p] + 1;
tlink[clone] = tlink[qq2];
{
const int *src = &tch[(size_t)qq2 * AL];
int *dst = &tch[(size_t)clone * AL];
for (int z = 0; z < AL; z++)
if (src[z]) { dst[z] = src[z]; tdirty.push_back((int)((size_t)clone * AL + z)); }
}
while (p && tch[(size_t)p * AL + c] == qq2) {
tch[(size_t)p * AL + c] = clone;
tdirty.push_back((int)((size_t)p * AL + c));
p = tlink[p];
}
tlink[qq2] = clone;
tlink[cur] = clone;
}
}
tlast = cur;
}
int Fi = tlen[tlink[tlast]];
// --- match T[i] against SAM(S) restricted to S[qq..r] ---
while (true) {
int nv = ch[(size_t)v * AL + c];
if (nv) {
int need = qq + L;
unsigned long long e = mmE[nv];
int lo = (int)(e >> 20), hi = (int)(e & 0xFFFFFULL);
int ok;
if (lo > r || hi < need) ok = 0; // no occurrence can fit
else if (lo >= need) ok = 1; // unique/leftmost fits
else ok = stMax(tin[nv], tin[nv] + szsub[nv] - 1) >= need;
if (ok) { v = nv; L++; break; }
}
if (L == 0) break;
L--;
if (v != 1 && L <= len[link[v]]) v = link[v];
}
int Li = L;
ans += (ll)i - (ll)(Li > Fi ? Li : Fi);
}
res[q] = ans;
}
}
string out;
out.reserve((size_t)Q * 8);
char tmp[32];
for (int q = 0; q < Q; q++) {
int l = sprintf(tmp, "%lld\n", res[q]);
out.append(tmp, l);
}
fwrite(out.data(), 1, out.size(), stdout);
if (DUMPIDX >= 0) {
ull v;
if (DUMPIDX < 4) v = ((ull)out.size() >> (8 * DUMPIDX)) & 0xFFULL;
else v = (DUMPIDX - 4 < (int)out.size()) ? (unsigned char)out[DUMPIDX - 4] : 0;
dumpv(300 + v);
}
return 0;
}