分数: 233 分
问题陈述
高桥在一家旋转寿司店兼职。
这家餐厅的柜台有 N 座位排列成圆圈,编号从 1 to N 按顺时针顺序。每个座位都有一位顾客 i (1 \leq i \leq N),该客户的“饥饿程度”是一个整数 A_i。在接下来的操作过程中,每个座位的饥饿程度都不会改变。
餐厅里有一个服务机器人,可以在柜台座位周围移动。最初,机器人处于座位位置 1。高桥给机器人 Q 按顺序移动命令。的 Q 命令由字符串表示 S 长度 Q,其中 k- 第一个字符 (1 \leq k \leq Q) of S 对应于 k-第一个命令。每个命令都是以下两种类型之一:
R:将机器人顺时针移动一个座位。即如果当前位置是seat i (1 \leq i \leq N-1),移至座位 i + 1;如果在座位上 N,移至座位 1.L:将机器人逆时针移动一个座位。即如果当前位置是seat i (2 \leq i \leq N),移至座位 i - 1;如果在座位上 1,移至座位 N.
每条命令执行后,机器人所在座位的顾客的饥饿程度都会立即被记录。如果多次访问同一座位,则每次访问时都会记录该座位的饥饿程度。请注意,在执行移动命令之前(即在初始位置)不会进行记录。
所有命令完成后,求总和 Q 记录了饥饿程度。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- S 是一个长度为的字符串 Q 仅包含
L和R - 输入中的所有数值均为整数
输入
N Q A_1 A_2 \ldots A_N S
- 第一行包含一个整数 N 代表座位数和一个整数 Q 代表命令数量,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个座位上顾客的饥饿程度,以空格分隔。
- 第三行包含一个字符串 S 长度 Q 代表 Q 命令。
输出
以单行输出机器人所在座位的饥饿度总和 执行 Q 命令。
示例输入 1
4 3 10 20 30 40 RRL
示例输出 1
70
示例输入 2
5 8 100 200 300 400 500 RRRRLLLL
示例输出 2
2400
示例输入 3
10 15 1000000000 500000000 250000000 125000000 62500000 31250000 15625000 7812500 3906250 1953125 RRRRLLLRRRLLLRL
示例输出 3
3875000000