Daring duck of mystery, Champion of right, Swoops out of the shadows, Darkwing owns the night. Somewhere some villain schemes, But his number’s up. Cloud of smoke and he appears, Master of surprise. Who’s that cunning mind behind That shadowy disguise? Nobody knows for sure, But bad guys are out of luck. ’Cause here comes Darkwing Duck! And Darkwing Duck needs your help, brother. Sometimes it’s very difficult to appear out of cloud of smoke exactly at place where bad guys are doing their bad business. Just imagine how difficult it is if Megavolt plans to attack the east side and Mr Banana Brain will surely appear in the west. The only thing we know is that villains always plan to do the max damage and we should decide what to do to stop them. City consists of some buildings in a line going from the east to the west. Darkwing Duck knows that the bad guys appear somewhere in the segment from \textbf{l}^th to \textbf{r}^th building, then move to the west destroying everything on their way and disappear somewhere on this segment. Intending to cause max damage for the first victim they always choose the most valuable building, if there are multiple choices, they choose the one with the most valuable next building to destroy, and so on, if there is still a tie, they try to destroy the maximum number of buildings. Help Darkwing Duck to find the exact place of the villains attack. \InputFile In the first line of input, there is a string consisting of English letters, digits and symbols "\textbf{,}", "\textbf{!}", "\textbf{_}", "\textbf{.}", "\textbf{--}" representing the town from the east to the west. Length of the string is no more than \textbf{500000} symbols. Value of the building is equal to ASCII code of symbol representing it! In the second line there is \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{500000}) --- the number of queries (villains attacks). In the next \textbf{N} lines of input there are numbers \textbf{1} ≤ \textbf{l_i} ≤ \textbf{r_i} --- segment of the possible villains attack (it’s guarantied that it is completely inside the string). Buildings are numbered starting from \textbf{1}. \OutputFile For every query you should print one number on the line: the starting point of the villains attack. And let the force be with you!