神秘的孤胆英雄，正义的化身，从阴影中飞掠而出，黑翼大侠主宰着黑夜。 某个角落有恶棍在密谋，但他的末日已临。 伴随着一团迷雾，他悄然现身，惊喜的大师。那个隐藏在神秘伪装背后的狡黠大脑是谁？没人能完全确定，但坏人们注定要倒霉了。 因为黑翼大侠来了！

而黑翼大侠需要你的帮助，兄弟。有时，要恰好在坏人干坏事的地方从烟雾中现身是非常困难的。想象一下，如果电击鼠（Megavolt）计划袭击东区，而香蕉脑先生（Mr Banana Brain）肯定会出现在西区，那该有多难。我们唯一知道的是，恶棍们总是计划造成最大的破坏，而我们必须决定如何阻止他们。

城市由一排从东向西排列的建筑物组成。黑翼大侠知道，坏人们会在第 $l$ 栋到第 $r$ 栋建筑物的区间内出现，然后向西移动，摧毁沿途的一切，并在该区间内的某个地方消失。为了对第一个受害者造成最大的伤害，他们总是选择价值最高的建筑物；如果有多种选择，他们会选择下一个要摧毁的建筑物价值最高的那一个，以此类推；如果仍然无法分出胜负，他们会尝试摧毁尽可能多的建筑物。请帮助黑翼大侠找到恶棍发起袭击的确切位置。

输入格式

输入的第一行是一个字符串，由英文字母、数字以及符号 ,、!、_、.、- 组成，代表从东到西的城镇。字符串的长度不超过 $500\,000$。建筑物的价值等于代表它的字符的 ASCII 码！

第二行包含一个整数 $N$ ($1 \le N \le 500\,000$) —— 询问（恶棍袭击）的数量。

接下来的 $N$ 行中，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i$) —— 表示可能发生恶棍袭击的区间（保证该区间完全在字符串范围内）。建筑物从 1 开始编号。

输出格式

对于每个询问，你应该在单行中输出一个数字：恶棍袭击的起点。愿原力与你同在！

样例

输入样例 1

Lets-get-dangerous!
3
1 19
3 8
15 18

输出样例 1

17
3
17