配点: 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