A. Combinatory logic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  1. if $$$x$$$ is a variable then $$$x$$$ is a combinatory term;
  2. if $$$c$$$ is a primitive function then $$$c$$$ is a combinatory term;
  3. if $$$A$$$ and $$$B$$$ are combinatory terms then (AB) is a combinatory term;
  4. there are no other combinatory terms.

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$$$:

  • $$$(Ia) = a$$$;
  • $$$((Ka)b) = a$$$;
  • $$$(((Sa)b)c) = ac(bc)$$$.

If we don't go deep into details of combinatory logic, we may compute the combinatory terms only using the following simple rules:

  1. find the leftmost combinator that can be computed;
  2. omit all left brackets behind the combinator with its pairs if they are present;
  3. apply the combinator by taking one or more next terms as parameters:
    • one term for combinator $$$I$$$

      $$$Ia = a$$$;

    • two terms for combinator $$$K$$$

      $$$Kab = a$$$;

    • three terms for combinator $$$S$$$

      $$$Sabc = ac(bc)$$$.

  4. if there are not enough terms to compute the combinator the term remains the same.

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.

Input

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

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.

Examples
Input
1
I
Output
a
Input
2
K
Output
a
Input
1
SII
Output
aa
Input
1
S(SII)I
Output
aaa
Input
3
S((S(KS)K)(S(KS)K)S)(KK)
Output
acb
Input
2
SS(K(SKK))
Output
abb