Чёрный Плащ
Отважная утка тайны, Чемпион справедливости, Выныривает из тени, Черный Плащ владеет ночью. Где-то злодей замышляет, Но его время вышло.
Облако дыма, и он появляется, Мастер неожиданности. Кто этот хитроумный ум за Этим таинственным маскарадом? Никто не знает наверняка, Но злодеям не повезло.
Потому что здесь Черный Плащ!
И Черному Плащу нужна твоя помощь, друг. Иногда очень сложно появиться из облака дыма именно в том месте, где злодеи занимаются своими грязными делами. Представь, как это трудно, если Мегавольт планирует атаку на восточной стороне, а Мистер Банановый Мозг наверняка появится на западе. Единственное, что мы знаем, это то, что злодеи всегда планируют нанести максимальный урон, и мы должны решить, что делать, чтобы их остановить. Город состоит из нескольких зданий в рядке, идущем с востока на запад. Черный Плащ знает, что злодеи появляются где-то в сегменте от l-го до r-го здания, затем двигаются на запад, уничтожая все на своем пути, и исчезают где-то на этом сегменте. Стремясь нанести максимальный урон первой жертве, они всегда выбирают самое ценное здание, если есть несколько вариантов, они выбирают то, у которого следующее здание для уничтожения самое ценное, и так далее, если все еще ничья, они пытаются уничтожить максимальное количество зданий. Помоги Черному Плащу найти точное место атаки злодеев.
Входные данные
В первой строке входных данных находится строка, состоящая из английских букв, цифр и символов ",", "!", "_", ".", "–", представляющая город с востока на запад. Длина строки не более 500000 символов. Значение здания равно ASCII-коду символа, представляющего его! Во второй строке находится N (1 ≤ N ≤ 500000) — количество запросов (атак злодеев). В следующих N строках входных данных находятся числа 1 ≤ l_i ≤ r_i — сегмент возможной атаки злодеев (гарантируется, что он полностью внутри строки). Здания нумеруются начиная с 1.
Выходные данные
Для каждого запроса вы должны вывести одно число в строке: начальную точку атаки злодеев. И да пребудет с вами сила!