小 $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$。

样例

input

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

output

4
7
6
2
8

样例二、三

见附件下载。

数据范围与提示

对于所有数据，满足 $1\le l_i\le r_i\le |a| \le 5 \times 10^{5}$，$1\le q \le 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$ 按顺序拼接的字符串。

hack

hack 数据必须保证 $type=0$。

时间限制：6s$\texttt{12s}$

空间限制：$\texttt{2GB}$