小 Z 和小 A 在玩扑克比大小。
他们玩的扑克比大小规则如下:
- 在游戏开始前,系统会给小 Z 和小 A 各发一堆手牌(两堆牌数量可能不相同),其中每张牌上写有一个小写字母。
- 在游戏的每一轮,小 Z 和小 A 同时翻开牌堆顶的第一张牌,若两人翻开的牌不同,则牌上对应小写字母更小的那一方获胜;若两人翻开的牌相同,则他们会将翻开的牌塞入牌堆底,继续游戏,直到某方获胜为止。
而系统实际上是从一个巨大的牌库里面发牌的,具体来说,假设牌库共有 n 张牌,分别是 a1,a2,⋯,an,则系统会随机选择第 l 张到第 r 张牌发给玩家,换言之,玩家从牌堆顶到牌堆底的牌分别是 al,al+1,⋯,ar。
现在小 Z 和小 A 一共要进行 q 轮游戏,并且小 Z 通过某种方式得知了系统在第 i 轮发给小 A 的牌为 ali,ali+1,⋯,ari,小 Z 想知道他一共有多少种可能的手牌能赢小 A。两堆手牌视为不同当且仅当两堆手牌数量不同,或存在一个位置 d 使得两堆手牌中距离堆顶为 d 的牌不同。
输入格式
从标准输入读入数据。
输入的第一行包含一个只包含小写字母的字符串 a 。
输入的第二行包含一个正整数 q 和一个整数 type,其中 type 表示数据类型。
接下来 q 行,第 i 行包含两个整数 li 和 ri。
输出格式
输出到标准输出。
输出 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≤li≤ri≤|a|≤5×105,1≤q≤5×105。
子任务 | 得分 | n≤ | q≤ | type |
---|---|---|---|---|
1 | 3 | 102 | 102 | 0 |
2 | 3 | 500 | 2000 | |
3 | 4 | 2000 | ||
4 | 5 | 2×104 | ||
5 | 13 | 105 | 105 | 3 |
6 | 17 | 0 | ||
7 | 15 | 5×105 | 5×105 | 1 |
8 | 15 | 2 | ||
9 | 25 | 0 |
数据类型 type 的含义为:
type=0,数据无特殊限制。
type=1,保证 ∃1≤l′≤r′≤|a|,ali,ri+ali,ri=al′,r′。
type=2,保证 ∀r′−l′=ri−li+1,若 al′,r′−1=ali,ri,则必有 ar′≠ali。
type=3,保证 ∑ri−li≤105。
其中 al,r 表示字符串 alal+1⋯ar;两个字符串 a+b 的结果为 a 和 b 按顺序拼接的字符串。