21737번 - SMUPC 계산기

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

[SMUPC 계산기의 동작 방식]

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

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

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

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

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

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