favorite We need a little bit of your help to keep things running, click on this banner to learn more


Fast Exponentiation

Very often arises the problem of effective calculation xn by given x and n, where n is a positive integer.

For example, assume that it is necessary to calculate the x16. You can simply start with 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 x2, x4, x8, x16.

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 xn, where "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 x2, x4, x5, x10, x11, x22, x23.

You need to formulate for a given n the corresponding rule for finding xn.


One positive integer n, not greater than 2·109.

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

Print the string for the rule how to raise x to power n to get xn.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Author Анатолий Присяжнюк
Source II этап Всеукраинской олимпиады школьников 2012-2013, г. Бердичев