Description：

给出一个字符串 $S$ ，第 $i$ 次询问 $S^\infty[li:ri]$ 的本质不同的子串个数。 $S^\infty$ 表示 $S$ 重复无数次形成的串。

$1\leqslant n\leqslant 10^5$

Solution：

首先如果 $S$ 是循环串，那么把它变成最短的循环节，这样不会影响答案，有一个结论，若 $len>n$ ，那么从 $1$ 到 $n$ 长度等于 $len$ 的 $n$ 个子串互不相同，证明的话就是如果有两个相同，会发现原串有循环节，但是循环节已经被去掉了，因此当 $r\geqslant 2n$ 时， $r$ 每增加一，答案就会增加 $n$ ，也就是从 $[1,n]$ 到 $r$ 这些串，因此我们只要计算区间本质不同子串个数就可以了。

考虑把所有询问离线，然后按右端点排序，每次右移右端点，考虑只在每个本质不同的子串出现在最右边的一次时计算，也就是 $Right$ 集合中最大的元素，再这一次出现的左端点处 $+1$ ，那么用线段树做一个区间求和就可以得到答案，每当右端点向右移动一格，考虑整个串构成的后缀自动机的变化，首先，从这个点到根的所有点的 $Right$ 集合的最大值都被更新成了这个点，发现这个和 $LCT$ 的 $access$ 操作非常接近，那么我们就可以用一个 $LCT$ 来维护它，在每一次轻重链切换的时候，从线段树上做一次区间减，减掉原来 $Right$ 集合的最大值，这是因为一条重链上的点 $Right$ 集合最大值一定是相同的，所以只是串长不同，而深度严格递增的一条链上代表的串长又是连续的，因此区间减就可以了，然后再做一次区间加更新答案就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

void print(ll k)

{

	if(k < 10){putchar(k + '0');return;}

	print(k / 10);putchar(k % 10 + '0');

	return;

}

#define MAXN 1800010

char c[MAXN];

int n,m;

struct query

{

	int l,r,id;

	ll ans;

}q[MAXN];

bool cmp_r(query a,query b){return a.r < b.r;}

bool cmp_id(query a,query b){return a.id < b.id;}

namespace ST

{

	ll c1[MAXN],c2[MAXN];

	inline int lowbit(int x){return x & (-x);}

	inline void add(int p,int k){for(register int i = p;i <= 3 * n;i += lowbit(i))c1[i] += k,c2[i] += p * k;return;}

	inline void add(int l,int r,int k)

	{

		if(l > r || !(1 <= l && l <= 3 * n && 1 <= r && r <= 3 * n))return;

		add(l,k);add(r + 1,-k);

		return;

	}

	inline ll query(int p)

	{

		register ll res = 0;

		for(register int i = p;i >= 1;i -= lowbit(i))res += 1ll * (p + 1) * c1[i] - c2[i];

		return res;

	}

	inline ll query(int l,int r){return query(r) - query(l - 1);}

}

namespace SAM

{

	struct node

	{

		int tr[26];

		int par,maxl;

	}s[MAXN << 1];

	int ptr = 1,root = 1,last = 1;

	inline int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	inline void extend(int k)

	{

		register int p = last;

		register int np = newnode(s[p].maxl + 1);

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			register int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				register int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

}

namespace LCT

{

	struct node

	{

		int c[2],fa;

		int maxl,minl,mx,mn,r;

	}t[MAXN << 1];

	inline bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

	inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

	inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	int pos[MAXN << 1];

	inline void pushdown(int rt)

	{

		if(t[rt].c[0] != 0)t[t[rt].c[0]].r = t[rt].r;

		if(t[rt].c[1] != 0)t[t[rt].c[1]].r = t[rt].r;

		return;

	}

	inline void maintain(int k)

	{

		t[k].mx = t[k].maxl;t[k].mn = t[k].minl;

		if(t[k].c[0] != 0)t[k].mx = max(t[k].mx,t[t[k].c[0]].mx),t[k].mn = min(t[k].mn,t[t[k].c[0]].mn);

		if(t[k].c[1] != 0)t[k].mx = max(t[k].mx,t[t[k].c[1]].mx),t[k].mn = min(t[k].mn,t[t[k].c[1]].mn);

		return;

	}

	inline void rotate(int x)

	{

		register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		maintain(y);maintain(x);

		return;

	}

	stack<int> s;

	inline void splay(int x)

	{

		s.push(x);

		for(register int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

		while(!s.empty()){pushdown(s.top());s.pop();}

		while(!isroot(x))

		{

			register int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	inline void access(int k,int r)

	{

		ST::add(1,r,1);

		for(register int i = 0;k;i = k,k = t[k].fa)

		{

			splay(k);

			t[k].c[1] = 0;

			maintain(k);

			ST::add(t[k].r - t[k].mx + 1,t[k].r - t[k].mn + 1,-1);

			t[k].r = r;

			t[k].c[1] = i;

			maintain(k);

		}

		return;

	}

}

void build()

{

	for(register int i = 2;i <= SAM::ptr;++i)

	{

		if(SAM::s[i].par != 1)LCT::t[i].fa = SAM::s[i].par;

		LCT::t[i].maxl = LCT::t[i].mx = SAM::s[i].maxl;

		LCT::t[i].minl = LCT::t[i].mn = SAM::s[SAM::s[i].par].maxl + 1;

	}

	return;

}

int nxt[MAXN];

int main()

{

	freopen("zifuchuan3-2.in","r",stdin);

	freopen("kkk.out","w",stdout);

	scanf("%s",c + 1);

	n = strlen(c + 1);

	for(register int i = 2,j = 0;i <= n;++i)

	{

		while(j && c[j + 1] != c[i])j = nxt[j];

		if(c[j + 1] == c[i])++j;

		nxt[i] = j;

	}

	if(n % (n - nxt[n]) == 0)n = n - nxt[n];

	for(register int i = 1;i <= 3 * n;++i)

	{

		SAM::extend(c[(i - 1) % n + 1] - 'a');

		LCT::pos[i] = SAM::last;

	}

	build();

	scanf("%d",&m);

	register int l,r;

	for(register int i = 1;i <= m;++i)

	{

		l = rd();r = rd();

		register int t = (l - 1) / n * n;

		l -= t;r -= t;

		if (r > l + n * 2)

        {

            q[i].ans = 1ll * (r - (l + n * 2)) * n;

            r = l + n * 2;

        }

        q[i].l = l;q[i].r = r;

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp_r);

	for(register int r = 1,p = 1;r <= 3 * n;++r)

	{

		LCT::access(LCT::pos[r],r);

		while(p <= m && q[p].r == r){q[p].ans += ST::query(q[p].l,q[p].r);++p;}

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)

	{

		print(q[i].ans);

		putchar('\n');

	}

	return 0;

}