6700: 字符串

给定由 a, b 两种小写字母组成的串 $s$, 下标从 $1$开始。

定义 $occ(t)$ 表示字符串 $t$ 在 $s$ 中出现的次数。

有 $q$ 次询问，每次询问有如下两种类型:

1. 操作1，给定 $l,r$，询问有多少本质不同的串 $t$，满足 $s[l,r]$ 是 $t$ 的子串，且 $occ(s[l,r])=occ(t)$

2. 操作2，给定 $l,r$，询问有多少本质不同的串 $t$，满足 $t$ 是 $s[l,r]$ 的子串，且 $occ(s[l,r])=occ(t)$

第一行一个整数 $t\ (1\le t\le 5)$ 代表数据组数。

对于每组数据:

第一行输入一个串 $s\ (1\le |s|\le 5\times 10^5)$ 。

第二行一个整数 $q\ (1\le q\le 5\times 10^5)$ 表示有 $q$ 次询问。

接下来 $q$ 行每行三个数 $op,l_0,r_0\ (op\in$ {$1,2$}$,1\le l_0,r_0\le |s|)$，分别表示询问的类型和询问的区间 $[l,r]$ 。

其中 $l=(l_0 + lastans - 1) \% |s| + 1$,$r=(r_0 + lastans - 1) \% |s| + 1$，保证$1\le l\le r\le |s|$ 。

$lastans$代表上一次询问的答案，特别的对于每组数据的第一次询问时$lastans=0$ 。

保证所有测试数据 $\sum |s|\le5\times 10^5,\sum q\le5\times 10^5$ 。

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