N (1 \leq N \leq 2 \cdot 10^5)마리의 거북이들이 원형으로 배열되어 있다.

각 거북이는 자신의 등껍질에 숫자 a_i (1 \leq a_i \leq 10^9)만큼의 에너지를 보유하고 있다.
모든 거북이들은 처음에 에너지가 가득 차 있다.

매 분마다 거북이들은 문자열 s_1s_2 \dots s_N에 따라 에너지를 교환한다.

만약 i번 거북이가 에너지가 적어도 1만큼 있으면,
s_i가 'L'이라면 왼쪽에 있는 거북이에게 1만큼 에너지를 전달하고,
'R'이라면 오른쪽에 있는 거북이에게 1만큼 에너지를 전달한다.

모든 교환은 동시에 일어난다. 즉, 거북이가 가득 찬 에너지를 가지고 있어도 1만큼 주고, 또 1만큼 받으면 에너지를 그대로 보존한다.

만약 거북이의 에너지가 a_i를 초과하면 초과한 에너지는 사라진다.

정올이는 M분 후에 모든 거북이들 사이에 남아있는 에너지의 총합을 알고 싶어한다. (1 \leq M \leq 10^9)

에너지 교환 timer 1s memory 1024MB

에너지 교환 1s 1024MB