6700: 字符串

给定由 `a`, `b` 两种小写字母组成的串 $ s $, 下标从 $1$开始。<br><br>定义 $ occ(t) $ 表示字符串 $ t $ 在 $ s $ 中出现的次数。<br><br>有 $ q $ 次询问，每次询问有如下两种类型:<br><br>1. 操作1，给定 $ l,r $，询问有多少本质不同的串 $t$，满足 $ s[l,r] $ 是 $ t $ 的子串，且 $ occ(s[l,r])=occ(t) $<br><br>2. 操作2，给定 $ l,r $，询问有多少本质不同的串 $t$，满足 $ t $ 是 $ s[l,r] $ 的子串，且 $ occ(s[l,r])=occ(t) $<br></div><div class=panel_bottom>&nbsp;</div>

第一行一个整数 $t\ (1\le t\le 5)$ 代表数据组数。<br><br>对于每组数据:<br><br>第一行输入一个串 $s\ (1\le |s|\le 5\times 10^5)$ 。<br><br>第二行一个整数 $q\ (1\le q\le 5\times 10^5)$ 表示有 $q$ 次询问。<br><br>接下来 $q$ 行每行三个数 $op,l_0,r_0\ (op\in$ {$1,2$}$,1\le l_0,r_0\le |s|)$，分别表示询问的类型和询问的区间 $[l,r]$ 。<br><br>其中 $l=(l_0 + lastans - 1) \% |s| + 1$,$r=(r_0 + lastans - 1) \% |s| + 1$，保证$1\le l\le r\le |s|$ 。<br><br>$lastans$代表上一次询问的答案，特别的对于每组数据的第一次询问时$lastans=0$ 。<br><br>保证所有测试数据 $\sum |s|\le5\times 10^5,\sum q\le5\times 10^5$ 。

对于每组数据输出 $q$ 行，每行一个整数表示每个询问的答案。