Description：

给出字符串 $S,T$ ，多次询问 $T$ 的一个子串 $T[l:r]$ 在 $S$ 的所有循环同构串的长度 为 $k$ 的前缀中出现过的字符串的数量。

$|S|,|T|,q\leqslant2\times10^5$

Solution：

首先把 $S$ 倍长和 $T$ 放在一起建立广义后缀自动机，那么我们每次询问就只要把 $T[l:r]$ 在 $SAM$ 上找到对应的位置回答询问，考虑答案是什么，我们可以把 $T[l:r]$ 在 $S$ 倍长的串中找出来，然后如果只考虑一个串，那么贡献应该是 $k-len(T[l:r])$ ，但是由于两个串之间可能相交，那么贡献就是 $\min(k-len(T[l:r]),\Delta)$ ， $\Delta$ 表示这个位置和上一个位置的差，如果只有一个节点的话，我们可以把所有的 $\Delta$ 插入两个树状数组中，一个维护值，另一个维护个数，然后每次就可以在上面查询，如果有多个查询的话，我们可以把所有询问离线挂在点上，然后用树上启发式合并的做法把子节点插在树状数组中就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 800010

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

#pragma GCC optimaze(3)

int q;

char S[MAXN],T[MAXN];

int l1,l2;

namespace SAM

{

	struct node

	{

		int tr[26];

		int maxl,par,rig;

	}s[MAXN << 2];

	bool tag[MAXN << 2];

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

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

	int pos[MAXN << 2];

	void extend(int k,int cur)

	{

		int p = last;

		if(s[p].tr[k])

		{

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

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

			else

			{

				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 = nq;

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

				last = nq;

			}

		}

		else

		{

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

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

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

			else

			{

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

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

				else

				{

					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;

		}

		if(cur)s[last].rig = cur;

		return;

	}

	struct edge

	{

		int to,nxt;

	}e[MAXN << 2];

	int edgenum = 0;

	int lin[MAXN << 2] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	void build()

	{

		for(int i = 2;i <= ptr;++i)add(s[i].par,i);

		return;

	}

	int f[MAXN << 2][20];

	void dfs(int k)

	{

		for(int i = 1;i <= 19;++i)f[k][i] = f[f[k][i - 1]][i - 1];

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			f[e[i].to][0] = k;

			dfs(e[i].to);

		}

		return;

	}

	int getpos(int l,int r)

	{

		int cur = pos[r];

		for(int i = 19;i >= 0;--i)if(s[f[cur][i]].maxl >= r - l + 1)cur = f[cur][i];

		return cur;

	}

}

struct BIT

{

	int c1[MAXN << 2],c2[MAXN << 2];

	#define N (2 * l1)

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

	void adds(int p,int x){++p;for(int i = p;i <= N;i += lowbit(i))c1[i] += x;return;}

	void addt(int p,int x){++p;for(int i = p;i <= N;i += lowbit(i))c2[i] += x;return;}

	int querys(int p){int res = 0;++p;for(int i = p;i >= 1;i -= lowbit(i))res += c1[i];return res;}

	int queryt(int p){int res = 0;++p;for(int i = p;i >= 1;i -= lowbit(i))res += c2[i];return res;}

}t;

#define iter set<int>::iterator

namespace QUERY

{

	struct query

	{

		int len,k,ans;

	}p[MAXN];

	vector<int> v[MAXN << 2];

	set<int> s;

	int judge = 0,crossx,crossy;

	int nowans;

	void change(int l,int r,int tag)

	{//cout << l << " " << r << " " << tag << endl;

		if(l < l1)return;

		if(l >= r)return;

		int k = r - l;

		t.adds(k,k * tag);

		t.addt(k,tag);

		nowans += k * tag;

		return;

	}

	int query(int k,int len)

	{//cout << "query " << k << " " << len << endl;

		int ans = nowans,val = k - len + 1;

		int q = t.querys(N) - t.querys(val),num = t.queryt(N) - t.queryt(val);

		ans = ans - q + num * val;//cout << q << " " << val << " " << num << endl;

		//cout << ans << " " << judge << " " << crossx << " " << crossy << endl;

		if(judge)

		{

			ans += crossy - l1;

			if(crossx + val - 1 < crossy)ans -= crossy - max(l1,crossx + val);

		}//cout << ans << endl;

		return ans;

	}

	void query(int k)

	{

		for(vector<int>::iterator it = v[k].begin();it != v[k].end();++it)

		{

			p[*it].ans = query(p[*it].k,p[*it].len);

		}

		return;

	}

	void insert(int val)

	{//cout << "insert " << val << endl;

		iter it = s.lower_bound(val);

		if(it != s.begin())

		{

			iter it_ = it;--it_;

			change(*it_,val,1);

			change(*it_,*it,-1);

		}

		change(val,*it,1);

		s.insert(val);

		it = s.lower_bound(l1);

		judge = 0;

		if(it != s.begin()){judge = 1;iter it_ = it;--it_;crossx = *it_;crossy = *it;}

		return;

	}

	void remove(int val)

	{//cout << "remove " << val << endl;

		s.erase(val);

		iter it = s.lower_bound(val);

		if(it != s.begin())

		{

			iter it_ = it;--it_;

			change(*it_,*it,1);

			change(*it_,val,-1);

		}

		change(val,*it,-1);

		it = s.lower_bound(l1);

		judge = 0;

		if(it != s.begin()){judge = 1;iter it_ = it;--it_;crossx = *it_;crossy = *it;}

		return;

	}

}

int dep[MAXN << 2],son[MAXN << 2],siz[MAXN << 2];

void dfs1(int k,int fa)

{

	using namespace SAM;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs1(e[i].to,k);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

	}

	return;

}

void add(int k)

{

	using namespace SAM;

	if(s[k].rig)QUERY::insert(s[k].rig);

	for(int i = lin[k];i != 0;i = e[i].nxt)add(e[i].to);

	return;

}

void del(int k)

{

	using namespace SAM;

	if(s[k].rig)QUERY::remove(s[k].rig);

	for(int i = lin[k];i != 0;i = e[i].nxt)del(e[i].to);

	return;

}

void dfs(int k)

{

	for(int i = SAM::lin[k];i != 0;i = SAM::e[i].nxt)

	{

		if(SAM::e[i].to == son[k])continue; 

		dfs(SAM::e[i].to);

		del(SAM::e[i].to);

	}

	if(son[k] != 0)dfs(son[k]);

	if(SAM::s[k].rig)QUERY::insert(SAM::s[k].rig);

	for(int i = SAM::lin[k];i != 0;i = SAM::e[i].nxt)

	{

		if(SAM::e[i].to != son[k])add(SAM::e[i].to);

	}

	QUERY::query(k);

	return;

}

int main()

{

	scanf("%s%s",S + 1,T + 1);

	l1 = strlen(S + 1),l2 = strlen(T + 1);

	for(int i = l1 + 1;i < l1 * 2;++i)S[i] = S[i - l1];

	for(int i = 1;i < l1 * 2;++i)SAM::extend(S[i] - 'a',i);

	SAM::last = 1;

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

	{

		SAM::extend(T[i] - 'a',0);

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

	}

	SAM::build();

	SAM::dfs(SAM::root);

	scanf("%d",&q);

	int l,r,k;

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

	{

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

		int pos = SAM::getpos(l,r);

		QUERY::p[i].len = r - l + 1;QUERY::p[i].k = k;

		QUERY::v[pos].push_back(i);

	}

	dfs1(1,1);

	QUERY::s.insert(2 * l1);

	dfs(1);

	for(int i = 1;i <= q;++i)printf("%d\n",QUERY::p[i].ans);

	return 0;

}