# Exponentiation

# Fast Exponentiation

Very often arises the problem of effective calculation `x`

by given ^{n}**x** and **n**, where **n** is a positive integer.

For example, assume that it is necessary to calculate the `x`

. You can simply start with ^{16}**x** and **15** times multiply it by **x**. But the same answer can be obtained in just four multiplication, if several times squared to obtain results consistently calculating `x`

, ^{2}`x`

, ^{4}`x`

, ^{8}`x`

.^{16}

The same idea is generally applicable to any value of **n** as follows. Write **n** as a number in the binary system (removing zeros from the left). Then replace each "**1**" with pair of characters **SX**, and each "**0**" with symbol **S** and delete the leftmost pair of characters "**SX**". The result is a rule for computing `x`

, where "^{n}**S**" is treated as a squaring operation, and "**X**" as the operation of multiplication by **x**. For example **n** = **23** has a binary representation **10111**. So we create a sequence **SXSSXSXSX**, from which we remove the first pair **SX** to get the final rule **SSXSXSX**. This rule says that it is necessary to "square, square, multiply by **x**, square, multiply by **x**, square and multiply by **x**", i.e. to calculate consistently the values `x`

, ^{2}`x`

, ^{4}`x`

, ^{5}`x`

, ^{10}`x`

, ^{11}`x`

, ^{22}`x`

.^{23}

You need to formulate for a given **n** the corresponding rule for finding `x`

.^{n}

#### Input

One positive integer **n**, not greater than **2**·`10`

.^{9}

#### Выходные данные

Print the string for the rule how to raise **x** to power **n** to get `x`

.^{n}

23

SSXSXSX