Combinatory logic

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Combinatory logic is a simple language that is used for descibing computational expressions. An expression consists of parentheses, variables and operators S and K. In this task we will consider only those expressions that do not contain variables. Write a program that will read in an expression in combinatory logic, reduce it (i.e. evaluate it as much as possible) and output the whole procedure.

The input contains a string consisting of letters S and K and validly-nested parentheses. Operators S and K act on other operators and expressions that follow them in the following way:

  • Kxy = x,
  • Sxyz = xz(yz),

where x, y and z represent some expressions. In an expression with multiple operators the evaluation is done from left to right. Examples of evaluation can be found in sample tests below.

The expression will not contain redundant parentheses. Parentheses are redundant if their removal does not change the meaning of the expression. In particular, we can always remove parenthesis that enclose a single symbol, e.g. expression (S) becomes S. Moreover, we can always remove left-aligned parentheses, e.g. (((SK)K)S)S becomes SKKSS. Another example: Some parentheses in the expression (S((KK)S(K))) can be removed so that the expression becomes S(KKSK).

If the operator S or K is not followed by a sufficient number of arguments, the evaluation can not be done. The argument is always the shortest non-empty string that follows the operator and is a valid expression. In the expression SK(SK)SK the (three) arguments of the first S operator are: K, (SK) and S. The last symbol (i.e. K) is not an argument of the S operator, since S only takes 3 arguments.

Task

Write a program that will read in an expression and reduce it. Your program should output the current expression after each single evaluation. If there are many possible operators that can be evaluated, you should always choose the the leftmost one. It is guaranteed that this procedure ends in a finite number of steps and that total size of the output will not exceed 20\,000 characters.

Input

The first line contains a string that is composed of letters S and K and validly-nested parentheses. The string will not contain unnecessary parentheses.

Input limits

The length of the string will not exceed 1000.

Output

Output all the steps in the procedure of reduction. The expressions in the output should not contain redundant parentheses. For the exact format see the examples below.

Output limits

The total size of the output will not exceed 20\,000 characters.

Examples

Input

SKKK

Output

SKKK
=KK(KK)
=K

Input

S(SK)(KS)(SKK)

Output

S(SK)(KS)(SKK)
=SK(SKK)(KS(SKK))
=K(KS(SKK))(SKK(KS(SKK)))
=KS(SKK)
=S

Input

SK

Output

SK

Input

S(KSK)

Output

S(KSK)
=SS

Input

S(KK)S

Output

S(KK)S

Comment

In the first example, we first evaluate the leftmost S operator, and then the leftmost K operator.

In the second example, we evaluate the leftmost operator in each step.

In the third example, none of the operators has a sufficient number of arguments, therefore the expression can not be reduced.

In the fourth example, the leftmost operator (namely, the S operator) has an insufficient number of arguments, therefore we evaluate the leftmost K operator.

In the fifth example, none of the operators has a sufficient number of arguments, therefore nothing can be reduced. The leftmost K operator only has one arguments, since its "scope" is only within the parentheses.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task