UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4453. cys就是要拿英魂!

统计 下载数据

Description

pps又开始dota视频直播了!一群每天被pps虐的蒟蒻决定学习pps的操作技术,他们把pps在这局放的技能记录了下
来,每个技能用一个字符表示。经过研究,蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最
强的连招。但是他们太弱了,不能学会整个视频里的连招,只能学会陈老师一段区间间内的连招,可是这个他们求
不出,于是只好向你求助。为了蒟蒻们不再被pps虐(怎么可能),请你帮帮他们。简化题意:给你一个字符串,
每次询问你一段区间的字典序最大的子串。

Input

第一行是一个字符串S,表示pps放的技能
第二行一个正整数Q,表示询问个数
接下来Q行,每行两个正整数[l,r],表示询问区间[l,r]中的字典序最大的子串。

Output

Q行,每行一个正整数,表示该区间内字典序最大的子串的起始位置。

Sample Input

Lets_go_mod_p!
5
2 2
3 3
2 5
1 10
2 9

Sample Output

2
3
3
3
3
数据范围:
1<=|S|<=100000
1<=Q<=100000
1<=l<=r<=|S|

Hint

Source