配点 : 700 点
問題文
(, ), +, -, *, a 仅由组成的数式 S 被给出(详情请参阅问题文后半部分)。S 包含在 a 的个数 N 被记作。
N 个整数 a_1, ..., a_N 和 2 个整数 (b_i, x_i) 组成的 Q 个查询被给出,请处理这些查询。
查询:在给定的数式中,从左数第 b_i 个 a 的 x_i ,从左数 1, ..., b_i-1, b_i+1, ..., N 个 a 分别替换为 a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N 的数式的值,以及将 10^9+7 作为模同余的 0 以上 10^9+6 以下整数输出。
在此问题中给出的数式 S 用如下 BNF 表示法的 <expr> 符号表示。
<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')'
制約
在给出的数式中包含的 a 的个数 N 被记作。
- S 的长度为 200\,000 以下
- S 可以用问题描述中的 BNF 表示法的
<expr>符号表示。输出 - 0 ≤ a_i < 10^9+7
- 1 ≤ Q ≤ 10^5
- 1 ≤ b_i ≤ N
- 0 ≤ x_i < 10^9+7
- x_i 是整数
入力
输入是按以下格式从标准输入给出的。
S Q a_1 ... a_N b_1 x_1 : b_Q x_Q
出力
Q 行。 i 行目 (1 ≤ i ≤ Q) 中输出第i 个查询的答案。例如,在第一个查询中,从左起
入力例 1
(a-(a))*a 4 0 1 2 1 1 1 2 2 1 1 4
出力例 1
0 2 1000000005 6
,从左起 1 个 a 使用 x_1 = 1 代入 2 个 a 使用 a_2 = 1 代入 3 个 a 使用 a_3 = 2 ,计算得到 (1-(1))*2 = 0 ,0 即为答案。
3 次数的查询中,从左边开始 1 个 a 使用 a_1 = 0 代入 2 个 a 使用 x_3 = 1 代入 3 个 a 使用 a_3 = 2 ,计算得到 (0-(1))*2 = -2 ,10^9+7 以...为模 -2 同余于... 0 以上 10^9+6 以下的整数是,10^9+5 即为答案。
入力例 2
(a)*a+((a+(a*(a))-(a)*a+a*a))*a 10 8 6 6 4 8 1 4 3 8 9 3 4 3 9 8 4 3 7 4 0 8 9 3 6 9 0 6 8 9 4
出力例 2
552 597 642 579 282 1002 570 354 318 462