Fast Exponentiation#2814

Fast Exponentiation

1 second

128 megabytes

Easy

Very often arises the problem of efficient calculation of $x^{n}$ x^n for given $x$ and $n$ , where $n$ is a positive integer.

For example, suppose it is necessary to calculate $x^{16}$ x^{16}. You can simply start with $x$ and multiply it by $x$ $15$ times. However, the same result can be obtained with just four multiplications by repeatedly squaring the result, consecutively calculating $x^{2}$ x^2, $x^{4}$ x^4, $x^{8}$ x^8, $x^{16}$ x^{16}.

The same idea can generally be applied to any value of $n$ as follows. Write $n$ in binary form (removing leading zeros). Then, replace each 1 with the pair of characters SX, each 0 with the character S, and remove the leftmost pair SX. The result is a rule for calculating $x^{n}$ x^n, where S denotes squaring, and X denotes multiplying by $x$ . For example, $n = 23$ n = 23 has binary representation 10111. Thus, we form the sequence SXSSXSXSX. Removing the initial pair SX gives the final rule SSXSXSX. This means: "square, square, multiply by $x$ , square, multiply by $x$ , square, and multiply by $x$ "; that is, consecutively calculate $x^{2}$ x^2, $x^{4}$ x^4, $x^{5}$ x^5, $x^{10}$ x^{10}, $x^{11}$ x^{11}, $x^{22}$ x^{22}, $x^{23}$ x^{23}.

You need to construct the rule for fast exponentiation of $x$ to the power $n$ for a given $n$ .

Input

One positive integer $n$ , not greater than $2 \cdot 1 0^{9}$ 2 \cdot 10^9.

Output

Print the string representing the rule for raising $x$ to the power $n$ to calculate $x^{n}$ x^n.

Examples

Example 1

Loading

x^{n}

x^{16}

x^{2}

x^{4}

x^{8}

x^{16}

x^{n}

n = 23

x^{2}

x^{4}

x^{5}

x^{10}

x^{11}

x^{22}

x^{23}

2 \cdot 1 0^{9}

x^{n}