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 lth to rth 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.
In the first line of input, there is a string consisting of English letters, digits and symbols ",", "!", "_", ".", "–" representing the town from the east to the west. Length of the string is no more than 500 000 symbols. Value of the building is equal to ASCII code of symbol representing it! In the second line there is N (1 ≤ N ≤ 500 000) — the number of queries (villains attacks). In the next N lines of input there are numbers 1 ≤ li ≤ ri — segment of the possible villains attack (it's guarantied that it is completely inside the string). Buildings are numbered starting from 1.
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!
## Input
In the first line of input, there is a string consisting of English letters, digits and symbols ",", "!", "_", ".", "–" representing the town from the east to the west. Length of the string is no more than 500 000 symbols. Value of the building is equal to ASCII code of symbol representing it! In the second line there is N (1 ≤ N ≤ 500 000) — the number of queries (villains attacks). In the next N lines of input there are numbers 1 ≤ li ≤ ri — segment of the possible villains attack (it's guarantied that it is completely inside the string). Buildings are numbered starting from 1.
## Output
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!
[samples]
**Definitions**
Let $ S $ be a string of length $ L \leq 500{,}000 $, where each character $ S[i] $ (for $ i \in \{1, \dots, L\} $) has value $ v_i = \text{ASCII}(S[i]) $.
Let $ N \in \mathbb{Z} $, $ 1 \leq N \leq 500{,}000 $, be the number of queries.
For each query $ j \in \{1, \dots, N\} $, we are given a segment $ [l_j, r_j] $, with $ 1 \leq l_j \leq r_j \leq L $.
**Constraints**
1. $ 1 \leq L \leq 500{,}000 $
2. $ 1 \leq N \leq 500{,}000 $
3. For each query $ j $: $ 1 \leq l_j \leq r_j \leq L $
**Objective**
For each query $ j $, find the starting index $ p_j \in [l_j, r_j] $ such that the villains choose the subsequence starting at $ p_j $ and proceeding westward (i.e., to higher indices) to maximize damage under the following lexicographic criteria:
- Maximize the value $ v_{p_j} $ (ASCII of first building).
- If tied, maximize $ v_{p_j+1} $ (ASCII of second building), if it exists.
- Continue this process for subsequent buildings in the segment $ [p_j, r_j] $.
- If still tied, maximize the number of buildings destroyed (i.e., choose the longest possible prefix).
Formally, among all non-empty prefixes of substrings $ S[l_j:r_j+1] $, select the one that is lexicographically maximum under the standard string comparison (by ASCII values), and return its starting index $ p_j $.