← 返回题目列表

Codeforces · 730/L

L. 表达式查询

中文机器翻译题面 查看原题

简化算术表达式 (SAE) 是由以下语法定义的算术表达式:

- <SAE> ::= <数字> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)
- <数字> ::= <数字> | <数字><数字>
- <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

换句话说,它是一个正确的算术表达式,允许包含括号、数字(可能带有前导零)、乘法和加法。例如,表达式“(0+01)”、“0”和“1*(0)”是简化的算术表达式,但表达式“2-1”、“+1”和“1+2)”则不是。

给定一个字符串 s1s2...s|s|代表 SAE; si 表示字符串的第 i 个字符,可以是数字 ('0'-'9')、加号 ('+')、乘号 ('*')、左圆括号 '(' 或右圆括号 ')'。

当且仅当它是 SAE 时,该字符串的一部分 slsl + 1...sr 称为子表达式。

你的任务是回答 m 个查询,每个查询都是一对整数 li, ri (1 ≤ li ≤ ri ≤ |s|)。对于每个查询,确定给定字符串的相应部分是否是子表达式,如果是子表达式,则计算其值模 1000000007 (109 + 7)。应使用标准操作员优先级来计算这些值。

输入

输入的第一行包含非空字符串 s (1 ≤ |s| ≤ 4·105),它表示正确的 SAE。字符串的每个字符可以是以下字符之一:'*'、'+'、'('、')' 或数字 ('0'-'9')。该表达式可能包含超大数字。

第二行包含一个整数m (1 ≤ m ≤ 4·105),它是查询的数量。接下来的 m 行中的每一行都包含两个以空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ |s|) — 第 i 个查询。

输出

第 i 个输出数应该是第 i 个查询的答案。如果第 i 个查询对应于有效的子表达式,则输出子表达式的值模 1000000007 (109 + 7)。否则输出 -1 作为查询的答案。在单独的行上打印数字。

示例

输入 #1

((1+2)*3+101*2)
6
8 14
1 6
2 10
11 14
5 5
4 5

输出 #1

205
-1
10
2
2
-1

输入 #2

(01)
1
1 4

输出 #2

1