원형 운동 구역의 기록

문제

한 헬스장은 운동 기구를 원형으로 배치하고, 회원이 안내 기록에 따라 운동하는 프로그램을 운영한다. 기구에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. 시계 방향에서 N번 다음은 1번이며, 반시계 방향에서 1번 다음은 N번이다. 기구가 하나뿐이면 어느 방향으로 이동해도 같은 기구에 도착한다. i번 기구에서 운동을 한 번 반복할 때 필요한 체력은 A_i다. 회원은 처음에 1번 기구에 있으며, 바라보는 이동 방향은 시계 방향이다. 체력의 최댓값은 H이고 처음 체력도 H다. 안내 기록에는 M개의 명령이 있으며, 반드시 입력된 순서대로 하나씩 처리한다. 명령을 처리하는 동안 아래에 적힌 변화 이외의 일은 일어나지 않는다. 특히 이동하거나 방향을 바꿀 때 체력이 줄어들지는 않는다. M x 명령은 현재 이동 방향으로 기구 사이를 x번 이동한다. F 명령은 이동 방향을 반대로 바꾸며 위치는 바꾸지 않는다. R x 명령은 체력을 x만큼 회복한다. 회복한 결과가 H보다 크면 체력은 H가 된다. W x 명령은 현재 기구에서 운동을 x번 반복하려는 시도다. 이 시도에 필요한 체력은 현재 기구의 A_i에 x를 곱한 값이다. W x 명령을 처리할 때 현재 체력이 필요한 체력 이상이면 시도에 성공한다. 필요한 체력 전부를 한꺼번에 차감하고 성공 횟수를 1 늘린다. 현재 체력이 부족하면 시도에 실패하며 실패 횟수를 1 늘린다. 실패한 경우에는 운동을 일부만 수행하지 않으며 체력도 줄어들지 않는다. 성공과 실패 모두 위치와 이동 방향은 바꾸지 않는다. 성공 횟수는 반복한 운동 수가 아니라 성공한 W 명령의 수다. 모든 명령을 처리한 뒤 회원이 있는 기구 번호, 남은 체력, 성공 횟수, 실패 횟수를 구한다. 결과는 명령에 따라 유일하게 정해진다. W 명령이 한 번도 없으면 성공 횟수와 실패 횟수는 모두 0이다.

입력

첫째 줄에 정수 N, M, H가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 A_1, ..., A_N이 주어진다. 다음 M개 줄에는 각각 F, M x, R x, W x 중 하나의 명령이 주어진다.
1 ≤ N ≤ 50,000, 1 ≤ M ≤ 30,000, 1 ≤ H ≤ 1,000,000,000이다. 모든 i에 대해 1 ≤ A_i ≤ 9이며, 모든 명령의 x는 1 이상 999 이하의 정수다.

출력

마지막 기구 번호, 남은 체력, 성공 횟수, 실패 횟수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

4 7 20
3 5 2 7
W 3
M 2
W 4
F
M 3
W 1
R 6

4 9 2 1

1 5 4
4
W 1
W 1
F
M 999
R 999

1 4 1 1

출처: Devin.KR 자체 제작