시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.2 초 (추가 시간 없음) 1024 MB 444 120 99 35.870%

문제

SMUPC를 기념하기 위해 ALGOS와 DSC Sookmyung에서는 SMUPC의 각 글자로 계산이 이루어지는 계산기를 만들었다. 가은이와 혜민이는 이 계산기와 같은 방식으로 작동하는 프로그램을 만들고자 한다. 가은이와 혜민이는 몇 가지 계산 작업을 통해 SMUPC에 해당하는 각 기호가 아래의 표와 같이 동작함을 밝혀낼 수 있었다.

[SMUPC 계산기의 동작 방식]

알파벳  S   M   U   P   C 
  해당 수식           -                 *        

/

   (정수 몫   

나눗셈)

        +        

여태까지의

계산 결괏값

반환

SMUPC 계산기는 기존의 사칙연산 방식과는 다르게 앞에서부터 순서대로 계산이 이루어진다. 단, 이 계산기에서 음수를 양수로 나누는 경우는 C++14의 기준을 따른다. 이는 음수에 -1을 곱해 양수로 바꾼 뒤 몫을 취하고, 그 몫에 -1을 곱한 것과 같다. 예를 들어, $5 / 3 = 1$, ($-5$) $/ 3 = -1$ 로 계산된다. 더불어 SMUPC 계산기에 입력하는 수식은 다음과 같은 규칙을 따라야 한다고 한다.

  • 수식은 0부터 9까지의 숫자와 SMUPC의 알파벳만을 포함할 수 있다.
  • 수식은 수로 시작해야 하며, 알파벳으로 끝나야 한다.
  • 수식에 음수를 입력할 수 없다.
  • 수식에 입력하는 수는 0으로 시작할 수 있다.
  • 알파벳 C로 계산 결괏값을 반환한 후에 추가적인 계산을 원한다면 알파벳 기호를 추가적으로 사용하여 입력을 이어나가야 한다.
  • 알파벳 SMUP는 서로 연속해서 입력할 수 없으며 알파벳 SMUP을 입력한 직후 다른 수의 입력 없이 알파벳 C를 바로 입력할 수 없다.

SMUPC 계산기와 같은 작업을 수행할 수 있는 프로그램을 작성하여라.

입력

첫째 줄에 수식에 들어갈 기호의 개수 $N$($ 1 \leq N \leq 500\,000$)이 주어진다.

둘째 줄에 $N$개의 기호가 사용된 수식이 주어진다. 수식의 길이는 $1\,000\,000$을 넘지 않는다. 단, 계산 도중 입력되는 수나 계산 결괏값의 범위는 $-2^{31}$ 이상 $2^{31}-1$ 이하이다. 더불어 어떤 수를 0으로 나누는 경우는 존재하지 않는다.

출력

알파벳 C가 나올 때마다 여태까지의 계산 결과 값을 띄어쓰기 간격으로 출력하도록 한다. 알파벳 C가 한번도 나오지 않을 경우 NO OUTPUT을 출력한다.

예제 입력 1

5
3S2M3U1P2C

예제 출력 1

5

예제 입력 2

4
0328CS00325CC

예제 출력 2

328 3 3

예제 입력 3

1
000232738S

예제 출력 3

NO OUTPUT