小 $Z$ 和小 $A$ 在玩扑克比大小。
他们玩的扑克比大小规则如下：
- 在游戏开始前，系统会给小 $Z$ 和小 $A$ 各发一堆手牌（两堆牌数量可能不相同），其中每张牌上写有一个小写字母。
- 在游戏的每一轮，小 $Z$ 和小 $A$ 同时翻开牌堆顶的第一张牌，若两人翻开的牌不同，则牌上对应小写字母更小的那一方获胜；若两人翻开的牌相同，则他们会将翻开的牌塞入牌堆底，继续游戏，直到某方获胜为止。
而系统实际上是从一个巨大的牌库里面发牌的，具体来说，假设牌库共有 $n$ 张牌，分别是 $a_1,a_2,\cdots,a_n$，则系统会随机选择第 $l$ 张到第 $r$ 张牌发给玩家，换言之，玩家从牌堆顶到牌堆底的牌分别是 $a_l,a_{l+1},\cdots,a_r$。
现在小 $Z$ 和小 $A$ 一共要进行 $q$ 轮游戏，并且小 $Z$ 通过某种方式得知了系统在第 $i$ 轮发给小 $A$ 的牌为 $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$，小 $Z$ 想知道他一共有多少种可能的手牌能赢小 $A$。两堆手牌视为不同当且仅当两堆手牌数量不同，或存在一个位置 $d$ 使得两堆手牌中距离堆顶为 $d$ 的牌不同。
输入格式
从标准输入读入数据。
输入的第一行包含一个只包含小写字母的字符串 $a$ 。
输入的第二行包含一个正整数 $q$ 和一个整数 $type$，其中 $type$ 表示数据类型。
接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。
输出格式
输出到标准输出。
输出 $q$ 行，每行一个整数表示小 $Z$ 有多少种可能的手牌能赢小 $A$。
样例数据
样例 1 输入
abbab 5 0 1 3 2 4 3 5 1 4 2 5
样例 1 输出
4 7 6 2 8
样例 2
见下发文件。
样例 3
见下发文件。
数据范围与提示
对于所有数据，满足 $1\le l_i\le r_i\le |a| \le 5 \times 10^{5}$，$1\le q \le 5 \times 10^{5}$。
| 子任务 | 得分 | $n\le$ | $q\le$ | $type$ |
|---|---|---|---|---|
| $1$ | $3$ | $10^{2}$ | $10^{2}$ | $0$ |
| $2$ | $3$ | $500$ | $2000$ | |
| $3$ | $4$ | $2000$ | ||
| $4$ | $5$ | $2 \times 10^{4}$ | ||
| $5$ | $13$ | $10^{5}$ | $10^{5}$ | $3$ |
| $6$ | $17$ | $0$ | ||
| $7$ | $15$ | $5 \times 10^{5}$ | $5 \times 10^{5}$ | $1$ |
| $8$ | $15$ | $2$ | ||
| $9$ | $25$ | $0$ |
数据类型 $type$ 的含义为：
$type=0$，数据无特殊限制。
$type=1$，保证 $\exists 1\le l'\le r'\le |a|$，$a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$。
$type=2$，保证 $\forall r'-l'=r_i-l_i+1$，若 $a_{l',r'-1}=a_{l_i,r_i}$，则必有 $a_{r'}\neq a_{l_i}$。
$type=3$，保证 $\sum r_i-l_i \le 10^5$。
其中 $a_{l,r}$ 表示字符串 $a_la_{l+1}\cdots a_r$；两个字符串 $a+b$ 的结果为 $a$ 和 $b$ 按顺序拼接的字符串。