33565번 - Starship Syncopation

문제

우주전함 스타십은 오늘도 별무리 사이를 항해한다. 지금은 운수가 좋지 않아 $N$척의 우주 해적선에 포위되고 말았지만... 스타십에는 별의 힘으로 작동하는 광자포가 탑재되어 있다. 이를 최대 출력으로 발사하면 우주 해적을 무찌르는 것쯤은 식은 죽 먹기다. 하지만 우주 항해 시대부터 전해져 오는 우주 전투 규칙에 따르면 이런 전법은 “낭만이 없기 때문에” 사용할 수 없다. 우주 전투 규칙을 중요시하는 스타십과 우주 해적은 다음의 방법으로 전투를 진행한다.

1. 전투 개시

   전투의 개시는 우주 해적이 스타십을 포위함으로써 선언된다. 이때 스타십은 저장해 두었던 별의 힘을 모두 잃는다. 각 우주 해적선에는 1ドル$ 이상 $N$ 이하의 서로 다른 정수 번호가 매겨져 있다. 우주 해적선마다 내구도가 정해져 있으며, 피해량이 내구도 이상이 되면 즉시 침몰한다. 스타십은 내구도가 매우 높아 아무리 큰 피해를 입어도 침몰하지 않는다.

2. 전투의 진행

   전투는 $T$개의 턴으로 구성되며, 실행 순서대로 1ドル$부터 $T$까지의 번호를 붙여 표기한다. 각 턴에는 별의 힘 저장, 스타십의 행동, 우주 해적선의 행동, 턴 종료가 순서대로 진행된다.

   1. 별의 힘 저장

      스타십이 별의 힘을 1ドル+($침몰한 우주 해적선의 수$)+($지금까지 별에 기도한 횟수$)$ 만큼 저장한다. 스타십에 저장할 수 있는 별의 힘의 최댓값은 1ドル,円 000,円 000$이다. 이를 초과하는 별의 힘을 저장한 경우, 초과분의 별의 힘은 사라진다.

   2. 스타십의 행동

      스타십이 다음 중 하나의 행동을 선택해 수행한다.

      • 대기하기

        아무것도 하지 않는다. 별의 힘을 소모하지 않는다.

      • 전함 수리

        스타십에 저장된 별의 힘을 3ドル$ 소모해 스타십이 받은 피해량을 3ドル$만큼 회복한다. 피해량을 초과해 회복하는 경우 초과한 회복량만큼 별의 힘을 돌려받는다. 스타십에 저장된 별의 힘이 3ドル$ 미만인 경우 대신 대기하기를 수행한다.

      • 별에 기도하기

        별의 힘을 7ドル$ 소모해 기도를 올린다. 저장된 별의 힘이 7ドル$ 미만인 경우 대신 대기하기를 수행한다.

      • 광자포 발사

        별의 힘을 5ドル$ 소모해 침몰하지 않은 우주 해적선 중 번호가 가장 작은 것에 5ドル$만큼 피해를 준다. 저장된 별의 힘이 5ドル$ 미만이면 대신 싱코페이션을 수행한다. 이 행동을 수행할 때 침몰하지 않은 우주 해적선이 항상 존재함을 증명할 수 있다.

      • 싱코페이션

        저장된 별의 힘을 모두 소모하고, 침몰하지 않은 우주 해적선 중 번호가 가장 작은 것에 소모한 별의 힘만큼 피해를 준다. 이번 턴 종료 시 광자포가 과부하 상태에 빠진다. 이 행동을 수행할 때 침몰하지 않은 우주 해적선이 항상 존재함을 증명할 수 있다. 광자포가 과부하 상태에 빠진 경우, 별의 힘 저장과 광자포 발사, 싱코페이션이 각각 다음과 같이 변경된다.

        • 별의 힘 저장 (과부하)

          기존과 동일하게 별의 힘 저장을 진행한 뒤, 스타십에 저장된 별의 힘이 10ドル$ 미만이 될 때까지 다음 두 행동을 번갈아 수행한다.

          • 침몰하지 않은 모든 우주 해적선과 스타십에 1ドル$의 피해를 준다.

          • 스타십에 저장된 별의 힘을 10ドル$ 소모한다.

        • 광자포 발사 (과부하)

          스타십에 저장된 별의 힘이 6ドル$ 이상인 경우, 저장된 별의 힘을 모두 소모해 그만큼 침몰하지 않은 모든 우주 해적선에 피해를 준다. 스타십에 저장된 별의 힘이 5ドル$ 이하인 경우, 광자포 발사에 실패하고 저장된 모든 별의 힘을 잃으며, 스타십이 5ドル$의 피해를 입는다. 그 뒤 광자포 발사의 성공 여부와 관계없이 광자포의 과부하 상태가 해제된다.

        • 싱코페이션 (과부하)

          저장된 모든 별의 힘을 잃고, 스타십이 5ドル$의 피해를 입는다. 그 뒤 광자포의 과부하 상태가 해제된다.

   3. 우주 해적선의 행동

      침몰하지 않은 모든 우주 해적선은 다음의 두 행동을 차례로 수행한다.

      1. 해적선의 현재 피해량이 0ドル$이라면 스타십에 피해를 1ドル$ 준다.

      2. 해적선의 현재 피해량이 1ドル$ 이상이라면 피해량을 1ドル$ 회복한다.

   4. 턴 종료

      이번 턴을 종료하고, 상황에 따라 전투를 종료하거나 다음 턴을 진행한다.

3. 전투 종료

   턴 종료 시 모든 우주 해적선이 침몰했거나, 총 $T$번의 턴 종료를 수행했다면 전투를 종료한다. 모든 우주 해적선이 침몰해 전투를 종료하는 경우 남은 턴은 진행되지 않음에 유의하라.

$T$턴 동안 스타십이 수행할 행동이 순서대로 주어진다. 턴의 번호가 주어졌을 때, 그 턴이 종료되었을 때의 전황을 출력하는 프로그램을 만들어 보자!

입력

첫째 줄에 우주 해적선의 수 $N$이 주어진다. (1ドル\le N\le 1,円 000,円 000$)

둘째 줄에 각 우주 해적선의 내구도를 나타내는 $N$개의 수가 공백으로 구분되어 주어진다. 그중 $i$번째 수는 $i$번 우주 해적선의 내구도다. 각 내구도는 1ドル$ 이상 1ドル,円 000,円 000$ 이하의 정수다.

셋째 줄에 전투에서 진행할 턴의 수 $T$가 주어진다. (1ドル\le T\le 202,円 500$)

넷째 줄에 길이 $T$의 문자열이 입력된다. 그중 $i$번째 문자는 $i$번째 턴에 스타십이 수행할 행동을 의미한다. 이때 W는 대기하기, R은 전함 수리, P는 별에 기도하기, L은 광자포 발사, S는 싱코페이션을 의미한다.

다섯째 줄에 질의의 수 $Q$가 주어진다. (1ドル\le Q\le 1,円 000$)

여섯째 줄에 질의로 턴의 번호를 나타내는 $Q$개의 정수 $t_1,ドル $t_2,ドル $\cdots,ドル $t_Q$가 오름차순으로 주어진다. (1ドル\le t_1<t_2<\cdots <t_Q\le T$)

출력

$Q$개의 줄에 걸쳐, $i$번째 줄에 $t_i$번째 턴 종료 시 스타십이 받은 피해량, 스타십에 저장된 별의 힘, 침몰하지 않은 우주 해적선의 수를 공백으로 구분해 출력한다.

만약 $t_i$번째 턴이 진행되지 않는다면 대신 $i$번째 줄에 skipped를 출력한다.

제한

힌트

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 다음은 대표적인 언어에서 빠른 입출력을 이용하는 방법입니다.

• C++: cin, cout을 사용한다면 main 함수 첫 줄에 std::cin.tie(0); std::cout.tie(0); std::ios::sync_with_stdio(false);를 추가하고, 줄바꿈 시 endl 대신 '\n'을 출력해주세요. 이 경우 scanf를 비롯한 C의 입출력 함수는 사용할 수 없음에 유의해 주세요.
  • scanf/printf는 충분히 빠르므로 별도의 처리를 하지 않아도 괜찮습니다.
• Java: Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용해 주세요.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해 주세요.