Description

pps又开始dota视频直播了！一群每天被pps虐的蒟蒻决定学习pps的操作技术，他们把pps在这局放的技能记录了下

来，每个技能用一个字符表示。经过研究，蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最

强的连招。但是他们太弱了，不能学会整个视频里的连招，只能学会陈老师一段区间间内的连招，可是这个他们求

不出，于是只好向你求助。为了蒟蒻们不再被pps虐（怎么可能），请你帮帮他们。简化题意：给你一个字符串，

每次询问你一段区间的字典序最大的子串。

Format

Input

第一行是一个字符串S，表示pps放的技能

第二行一个正整数Q，表示询问个数

接下来Q行，每行两个正整数[l,r]，表示询问区间[l,r]中的字典序最大的子串。

Output

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

Samples

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

2
3
3
3
3

Limitation

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