Темний плащ
Сміливий качур таємниць, Чемпіон справедливості, Вихоплюється з тіні, Темнокрило володіє ніччю. Десь якийсь лиходій замишляє, Але його номер вже відомий.
Хмара диму і він з'являється, Майстер сюрпризу. Хто ж цей хитрий розум за тією тіньовою маскою? Ніхто не знає напевно, Але поганцям не пощастило.
Бо ось іде Темнокрило Качур!
І Темнокрило Качур потребує твоєї допомоги, друже. Іноді дуже важко з'явитися з хмари диму саме в тому місці, де поганці займаються своїми темними справами. Просто уяви, як важко, якщо Мегавольт планує атакувати східну сторону, а Містер Бананова Мозок обов'язково з'явиться на заході. Єдине, що ми знаємо, це те, що лиходії завжди планують завдати максимальних збитків, і ми повинні вирішити, що робити, щоб їх зупинити. Місто складається з деяких будівель у рядку, що йде зі сходу на захід. Темнокрило Качур знає, що поганці з'являються десь у сегменті від l-го до r-го будинку, потім рухаються на захід, знищуючи все на своєму шляху, і зникають десь на цьому сегменті. Намірюючись завдати максимальних збитків першій жертві, вони завжди обирають найціннішу будівлю, якщо є кілька варіантів, вони обирають ту, у якої наступна будівля найцінніша для знищення, і так далі, якщо все ще є нічия, вони намагаються знищити максимальну кількість будівель. Допоможи Темнокрилу Качуру знайти точне місце атаки лиходіїв.
Вхідні дані
У першому рядку введення знаходиться рядок, що складається з англійських літер, цифр та символів ",", "!", "_", ".", "–", що представляють місто зі сходу на захід. Довжина рядка не перевищує 500000 символів. Вартість будівлі дорівнює ASCII-коду символу, що її представляє! У другому рядку знаходиться N (1 ≤ N ≤ 500000) — кількість запитів (атак лиходіїв). У наступних N рядках введення знаходяться числа 1 ≤ l_i ≤ r_i — сегмент можливої атаки лиходіїв (гарантовано, що він повністю знаходиться всередині рядка). Будівлі нумеруються, починаючи з 1.
Вихідні дані
Для кожного запиту ви повинні вивести одне число в рядку: початкову точку атаки лиходіїв. І нехай сила буде з вами!