/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は回転寿司店でアルバイトをしています。
この店のカウンターには N 個の座席が円形に配置されており、座席には時計回りに 1 から N までの番号が付けられています。座席 i (1 \leq i \leq N) にはお客さんが座っており、そのお客さんの「空腹度」は整数 A_i です。各座席の空腹度は、以降の操作を通じて変化しません。
店内にはサービスロボットがあり、カウンターの座席を巡回します。最初、ロボットは座席 1 の位置にいます。高橋君はロボットに Q 回の移動命令を順に出します。Q 回の命令は長さ Q の文字列 S で表され、S の k 文字目 (1 \leq k \leq Q) が k 回目の命令に対応します。各命令は以下の2種類のいずれかです：
R：ロボットを時計回りに 1 つ移動する。すなわち、現在位置が座席 i (1 \leq i \leq N-1) なら座席 i + 1 に、座席 N なら座席 1 に移動する。L：ロボットを反時計回りに 1 つ移動する。すなわち、現在位置が座席 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 は
LとRのみからなる長さ Q の文字列である - 入力中の数値はすべて整数である
入力
N Q A_1 A_2 \ldots A_N S
- 1 行目には、座席の数を表す整数 N と、命令の回数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目には、各座席のお客さんの空腹度を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 3 行目には、Q 回の命令を表す長さ Q の文字列 S が与えられる。
出力
Q 回の命令それぞれの実行直後にロボットがいる座席の空腹度の総和を、1 行で出力せよ。
入力例 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
Score : 233 pts
Problem Statement
Takahashi works part-time at a revolving sushi restaurant.
The counter in this restaurant has N seats arranged in a circle, numbered from 1 to N in clockwise order. A customer is seated at each seat i (1 \leq i \leq N), and that customer's "hunger level" is an integer A_i. The hunger level of each seat does not change throughout the following operations.
There is a service robot in the restaurant that travels around the counter seats. Initially, the robot is at the position of seat 1. Takahashi gives the robot Q movement commands in sequence. The Q commands are represented by a string S of length Q, where the k-th character (1 \leq k \leq Q) of S corresponds to the k-th command. Each command is one of the following two types:
R: Move the robot one seat clockwise. That is, if the current position is seat i (1 \leq i \leq N-1), move to seat i + 1; if at seat N, move to seat 1.L: Move the robot one seat counterclockwise. That is, if the current position is seat i (2 \leq i \leq N), move to seat i - 1; if at seat 1, move to seat N.
Immediately after each command is executed, the hunger level of the customer at the seat where the robot is located is recorded. If the same seat is visited multiple times, the hunger level of that seat is recorded each time it is visited. Note that no recording takes place before the movement commands are executed (i.e., at the initial position).
After all commands have been completed, find the sum of the Q recorded hunger levels.
Constraints
- 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 is a string of length Q consisting only of
LandR - All numerical values in the input are integers
Input
N Q A_1 A_2 \ldots A_N S
- The first line contains an integer N representing the number of seats and an integer Q representing the number of commands, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the hunger levels of the customers at each seat, separated by spaces.
- The third line contains a string S of length Q representing the Q commands.
Output
Output in a single line the sum of the hunger levels at the seats where the robot is located immediately after each of the Q commands is executed.
Sample Input 1
4 3 10 20 30 40 RRL
Sample Output 1
70
Sample Input 2
5 8 100 200 300 400 500 RRRRLLLL
Sample Output 2
2400
Sample Input 3
10 15 1000000000 500000000 250000000 125000000 62500000 31250000 15625000 7812500 3906250 1953125 RRRRLLLRRRLLLRL
Sample Output 3
3875000000