题目描述

小 Z 和小 A 在玩扑克比大小。

规则如下：

• 系统给双方各发一堆手牌（数量可能不同），每张牌有一个小写字母
• 每轮同时翻开牌堆顶的第一张牌：
  • 若牌不同，字母更小的一方获胜
  • 若牌相同，将翻开的牌塞入牌堆底，继续游戏直到某方获胜

系统从牌库发牌：假设牌库有 $n$ 张牌 $a_1,a_2,\cdots,a_n$，系统选择第 $l$ 张到第 $r$ 张牌发给玩家（牌堆顶到牌堆底为 $a_l,a_{l+1},\cdots,a_r$）

现在进行 $q$ 轮游戏，小 Z 知道小 A 在第 $i$ 轮的牌为 $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$，求小 Z 有多少种可能的手牌能赢小 A。

两堆手牌视为不同当且仅当：

1. 手牌数量不同，或
2. 存在位置 $d$ 使得距离堆顶为 $d$ 的牌不同

输入格式

第一行：一个只包含小写字母的字符串 $a$

第二行：正整数 $q$ 和整数 $type$（数据类型）

接下来 $q$ 行：每行两个整数 $l_i$ 和 $r_i$

输出格式

输出 $q$ 行，每行一个整数表示小 Z 可能赢的手牌种数

样例 1

输入

abbab
5 0
1 3
2 4
3 5
1 4
2 5

输出

4
7
6
2
8

样例 2

见附加文件中的 与

样例 3

见附加文件中的 与

数据范围与提示

对于所有数据：$1 \leq l_i \leq r_i \leq |a| \leq 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$

数据类型 $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$ 按顺序拼接。