Combinatory logic is a field in mathematical logic developed in the first half of the $$$XX$$$ century by Moses Sheinfinkel and Haskell Curry. Main elements of combinatory logic are constants, variables and terms. To construct terms we use the following induction rules:
The expression $$$(AB)$$$ means the operation of applying function (combinator) $$$A$$$ to its argument $$$B$$$. To shorten the notations, the expression may have omitted brackets, if so they can be recovering by applying associativity rule:
$$$$$$ABC = ((AB)C).$$$$$$
So according the rule above, let's assume that the expression $$$ABC$$$ is also the correct form of combinatory term.
Let's note variables as lowercase letters and combinators as uppercase letters. In the problem only the combinators can be constants.
Now let's define the simple combinators $$$I$$$, $$$K$$$, and $$$S$$$:
If we don't go deep into details of combinatory logic, we may compute the combinatory terms only using the following simple rules:
$$$Ia = a$$$;
$$$Kab = a$$$;
$$$Sabc = ac(bc)$$$.
Let's consider some more examples:
$$$$$$S(KII)ab = (KII)b(ab) = (I)b(ab) = Ib(ab) = b(ab);$$$$$$
$$$$$$SIISa = IS(IS)a = S(IS)a = S(S)a = SSa;$$$$$$
$$$$$$ \begin {array} {cc} S(KK)I(Kab)b = (KK)(Kab)(I(Kab))b = KK(Kab)(I(Kab))b = \\ = K(I(Kab))b = (I(Kab)) = I(Kab) = (Kab) = (a). \end{array} $$$$$$
Given the combinator $$$P$$$ written by using primitive combinators $$$I$$$, $$$K$$$, $$$S$$$ and brackets. Compute the application of $$$P$$$ to the sequence containing the first $$$n$$$ lowercase Latin letters.
The first line contains one integer number $$$n$$$ ($$$1 \leq n \leq 8$$$). The second line contain the description of combinator $$$P$$$ (the string of symbols "I", "K", "S", "(" and ")" ). $$$P$$$ must be a combinatory term. The length of string is at least $$$1$$$ and at most $$$150\, 000$$$. The maximum nesting level of brackets does not exceed $$$100$$$. The total number of applied combinators in computation does not exceed $$$50\, 000$$$.
Output the resulting string of application of $$$P$$$ to the sequence of the first $$$n$$$ Latin letters. It is guaranteed, that the string length will not exceed $$$8$$$ and it will contain only lowercase Latin letters.
1 I
a
2 K
a
1 SII
aa
1 S(SII)I
aaa
3 S((S(KS)K)(S(KS)K)S)(KK)
acb
2 SS(K(SKK))
abb