8453: BZOJ4453：cys就是要拿英魂！

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

输入格式

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

输出格式

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

样例输入

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

样例输出

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

提示

没有写明提示

题目来源

没有写明来源