← 返回题目列表

AtCoder · iroha2019_day2_j

J. 在黑麦田里等待时

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

配点: 900 点

問題文

青木和高桥约好一起玩,但等呀等,高桥没有来,于是决定进行如下游戏。

  • N 张红卡和 N-1 张蓝卡,交替排列成一列。也就是说,先将红卡排列成一列,在相邻红卡之间放置蓝卡。
  • 从左边开始 i 第…张红色卡片上,最初写着非负整数 A_i 写着。
  • 从左边开始 i 第…张蓝色卡片上,在一面上 + 的另一方面是 × 写着。S_i 是 + 保证可以在 + 的面,S_i 是 * 保证可以在 × 的一面最初是正面。
  • 青木先生,Q 按编号顺序执行一个查询。i 第几个查询的内容是 3 个非负整数 T_i, X_i, Y_i 表示,并解释如下。
    • T_i = 1 时,从左边起 X_i 第几张红色卡片上写的整数 Y_i 改写为。
    • T_i = 2 时,从左边起 X_i 第几张蓝色卡片翻过来。在这个查询中,Y_i = 0 得到保证。
    • T_i = 3 时(回答查询),从左边起 X_i 第 n 张红色卡片放在左端,Y_i 第 n 张红色卡片放在右端的部分卡片序列视为数学式,并回答其计算结果。不过,由于青木先生无法在没有纸和笔的情况下计算大数,10^9+7 的余数作为答案。

为了确认青木先生的答案是否正确,彩叶酱决定编写一个程序来模拟上述游戏。

制約

  • S 满足 +和* 仅由…组成的长度 N-1 的字符串,其它都是整数
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq Q \leq 10^5
  • 各質問 T_i,\ X_i,\ Y_i 关于以下 3 中的任意一个成立
    • T_i = 1,\ 1 \leq X_i \leq N,\ 0 \leq Y_i \leq 10^9
    • T_i = 2,\ 1 \leq X_i \leq N - 1,\ Y_i = 0
    • T_i = 3,\ 1 \leq X_i \leq Y_i \leq N

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N
S
Q
T_1 X_1 Y_1
\vdots
T_Q X_Q Y_Q

出力

请将各个回答kueri的正确答案分别 1 按行顺序输出。


入力例 1

5
1 2 3 4 100
**+*
5
3 1 4
1 5 5
3 4 5
2 1 0
3 1 5

出力例 1

10
20
27

1行中,1\times2\times3+4=10。+或×如同普通的四则运算一样计算。


入力例 2

30
141056031 626562406 398984580 302301632 724833823 819260147 433302050 210081 464012738 867417506 592634049 207581070 196502965 201049574 651294024 481261837 785858015 132486153 389688195 704728852 193622905 503147306 35766369 884292216 743597128 172030481 568485269 51112624 850324303 618492623
**+**++++*+***+*++******++*++
30
3 8 9
2 21 0
1 18 32689954
2 27 0
2 28 0
3 5 23
3 3 3
1 19 705926811
3 19 21
2 8 0
2 20 0
3 8 25
2 2 0
1 23 249011956
3 4 17
2 2 0
2 2 0
3 15 23
3 1 16
2 2 0
3 20 28
3 17 21
1 25 300797469
2 14 0
3 6 30
3 4 28
2 10 0
1 5 102545023
1 30 895902786
3 1 30

出力例 2

464222819
10116361
398984580
494861147
781529391
919851764
726060889
72956646
887945392
641812930
620768060
243676249
751282029

解説

解説